01BFS与DIJ的应用实例

原题链接：61280.资料夹

hjh-已被收容

2025-08-06 16:48:34

发布于：浙江

4阅读

0回复

0点赞

DIJ

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

// 四个对角线移动方向：{右下，左下，右上，左上}
vector<pair<int, int> > directions =
        {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

// 节点结构体：记录位置和移动方向
struct Node {
    int x, y; // 当前坐标
    int direction; // 移动方向索引(0-3)，4表示初始无方向
    int dis;
};

struct cmp {
    bool operator()(Node a, Node b) {
        return a.dis > b.dis;
    }
};

// 5
// 1 3
// 3 5
// ....#
// ...#.
// .....
// .#...
// #....
int main() {
    int n;
    cin >> n;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    vector<string> mp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> mp[i];
        mp[i] = " " + mp[i];
    }
    vector<vector<vector<int> > > dis(n + 1, vector<vector<int> >(n + 1, vector<int>(5, 1e9)));
    vector<vector<vector<int> > > vis(n + 1, vector<vector<int> >(n + 1, vector<int>(5)));
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({x1, y1, 4, 0});
    dis[x1][y1][4] = 0;
    while (!pq.empty()) {
        auto node = pq.top();
        pq.pop();
        int xx1 = node.x, yy1 = node.y, di = node.direction, diss = node.dis;
        if (vis[xx1][yy1][di]) continue;
        vis[xx1][yy1][di] = 1;
        if (xx1 == x2 && yy1 == y2) {
            cout << diss << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int new_x = xx1 + directions[i].first,
                    new_y = yy1 + directions[i].second,
                    new_diss = diss + (i != di),
                    new_di = i;
            if (new_x <= n && new_x >= 1 && new_y <= n && new_y >= 1
                && mp[new_x][new_y] == '.' && dis[new_x][new_y][new_di] > new_diss) {
                dis[new_x][new_y][new_di] = new_diss;
                pq.push({new_x, new_y, new_di, new_diss});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

01DFS

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

vector<pair<int, int> > dd = {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

struct node {
    int x, y, d;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    deque<node> q;
    vector<vector<vector<int> > > dis(n + 1, vector<vector<int> >(n + 1, vector<int>(5, 1e9)));

    vector<string> mp(n + 1);
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++) {
        cin >> mp[i];
        mp[i] = " " + mp[i];
    }
    q.push_front({x1, y1, 4});
    dis[x1][y1][4] =0 ;
    while (!q.empty()) {
        auto f = q.front();
        q.pop_front();
        int x = f.x, y = f.y, d = f.d, tim = dis[x][y][d];
       // cout <<x<<" "<<y <<" " << d<<" "<<time<<endl;
        if (x == x2 && y == y2) {
            cout << tim << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int dx = x + dd[i].first;
            int dy = y + dd[i].second;
            int dt = tim + (i != d);
            //cout <<dx<<" "<< dy <<" "<<dt/<<endl; 
            if (dx >= 1 && dx <= n && dy >= 1 && dy <= n &&mp[dx][dy] =='.'&& dis[dx][dy][i] > dt) {
                  //cout <<dx<<" "<< dy <<" "<<dt <<" " <<i<<endl;
                dis[dx][dy][i] = dt;
                if (i == d) {
                    q.push_front({dx, dy, i});
                } else {
                    q.push_back({dx, dy, i});
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论