acwing1076. 迷宫问题（bfs）

给定一个 n×nn×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。
接下来 nn 行，每行包含 nn 个整数 0 或 1，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)(0,0)，右下角坐标为 (n−1,n−1)(n−1,n−1)。

数据范围

0≤n≤10000≤n≤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

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int g[N][N];
PII q[N*N];
PII pre[N][N];
int n;
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
void bfs(int sx, int sy) {
    int hh = 0, tt = 0;
    q[0] = {sx,sy};
    //判重
    memset(pre,-1,sizeof pre);
    pre[sx][sy] = {0,0};
    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 4; ++i) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            //之前更新过
            if (pre[a][b].x != -1) continue;
            if (g[a][b] == 1) continue;
            q[++tt] = {a,b};
            pre[a][b] = {t.x,t.y};
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            cin >> g[i][j];
    //倒着搜，输出路径就是正着
    bfs(n-1,n-1);
    PII end(0,0);
    while (true) {
        cout << end.x << " " << end.y << endl;
        if (end.x == n-1 && end.y == n-1) break;
        end = pre[end.x][end.y];
    }
    return 0;
}