<—点个赞吧QwQ

宣传一下算法提高课整理

给定一个 $n \times n$ 的二维数组，如下所示：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 n。

接下来 $n$ 行，每行包含 $n$ 个整数 0 或 1，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 $(0,0)$，右下角坐标为 $(n-1,n-1)$。

数据范围

$0 \le n \le 1000$

输入样例：

5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

思路

这题要打印方案，为了好写代码，我们采用倒着搜。
由于要打印方案，我们把从$(n,n)$到$(1,1)$（这里我喜欢从$1$开始）的每一个点的前一个遍历到的点，就是从$(1,1)$到$(n,n)$这一些点的后一个点！！！
还有一点：$BFS$第一次搜到的点一定是距离最短的！！！
所以在输出时答案不需要反转。

代码

#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010;
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
int n;
int g[N][N];
PII pre[N][N];
void bfs () {
    queue <PII> q;
    q.push ({n,n});
    memset (pre,-1,sizeof (pre));
    pre[n][n] = {1,1};
    while (!q.empty ()) {
        PII t = q.front ();
        q.pop ();
        for (int i = 0;i < 4;i++) {
            int a = t.x + dx[i],b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > n) continue;
            if (g[a][b]) continue;
            if (pre[a][b].x != -1) continue;
            q.push ({a,b});
            pre[a][b] = t;
        }
    }
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) cin >> g[i][j];
    }
    bfs ();
    PII end = {1,1};
    while (true) {
        cout << end.x - 1 << ' ' << end.y - 1 << endl;
        if (end.x == n && end.y == n) break;
        end = pre[end.x][end.y];
    }
    return 0;
}