3.走迷宫 BFS

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int, int> PII;
 4 queue<PII> q;
 5 int n, m;
 6 const int N = 110;
 7 int mp[N][N];
 8 int d[N][N]; //存储每一个点到起点的距离
 9 int bfs() {
10     int dx[4] = {-1, 0, 1, 0};
11     int dy[4] = {0, 1, 0, -1};
12     while (!q.empty()) {
13         PII t = q.front(); //取出队头
14         q.pop(); //弹出队头
15         for (int i = 0; i < 4; i++) { //尝试向四个方向扩展
16             int x = t.first + dx[i];
17             int y = t.second + dy[i];
18             if (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] == 0 && d[x][y] == -1) { //并且这个点还没有走过的话
19                 d[x][y] = d[t.first][t.second] + 1;
20                 q.push({x, y});
21             }
22         }
23     }
24     return d[n - 1][m - 1];
25 }
26 int main() {
27     cin >> n >> m;
28     for (int i = 0; i < n; i++) {
29         for (int j = 0; j < m; j++) {
30             cin >> mp[i][j];
31         }
32     }
33     memset(d, -1, sizeof(d));
34     d[0][0] = 0;
35     q.push({0, 0});
36     cout << bfs() << endl;
37     return 0;
38 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int, int> PII;
 4 queue<PII> q;
 5 int n, m;
 6 const int N = 110;
 7 int mp[N][N];
 8 int d[N][N]; //存储每一个点到起点的距离
 9 PII p[N][N];
10 int bfs() {
11     int dx[4] = {-1, 0, 1, 0};
12     int dy[4] = {0, 1, 0, -1};
13     while (!q.empty()) {
14         PII t = q.front(); //取出队头
15         q.pop(); //弹出队头
16         for (int i = 0; i < 4; i++) { //尝试向四个方向扩展
17             int x = t.first + dx[i];
18             int y = t.second + dy[i];
19             if (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] == 0 && d[x][y] == -1) { //并且这个点还没有走过的话
20                 d[x][y] = d[t.first][t.second] + 1;
21                 q.push({x, y});
22                 p[x][y] = t;
23             }
24         }
25     }
26     int x = n - 1, y = m - 1;
27     while (x != 0 || y != 0) {
28         cout << x << " " << y << endl;
29         PII t = p[x][y];
30         x = t.first, y = t.second;
31     }
32     return d[n - 1][m - 1];
33 }
34 int main() {
35     cin >> n >> m;
36     for (int i = 0; i < n; i++) {
37         for (int j = 0; j < m; j++) {
38             cin >> mp[i][j];
39         }
40     }
41     memset(d, -1, sizeof(d));
42     d[0][0] = 0;
43     q.push({0, 0});
44     cout << bfs() << endl;
45     return 0;
46 }