给定一个 n×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≤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 <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10;
int g[N][N];
PII pre[N][N];
int st[N][N];
int n;
int ne[4][2] = {
{-1, 0}, {1, 0}, {0, 1}, {0, -1}};void bfs(int sx, int sy)
{queue<PII> qu;qu.push({sx, sy});st[sx][sy] = 1;while (qu.size()){PII t = qu.front();qu.pop();for (int i = 0; i < 4; i++){int dx = t.first + ne[i][0], dy = t.second + ne[i][1];if (dx < 0 || dx > n - 1 || dy < 0 || dy > n - 1)continue;if (st[dx][dy])continue;if (g[dx][dy])continue;qu.push({dx, dy});st[dx][dy] = 1;pre[dx][dy] = t;}}
}
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 now = {0, 0};while (1){cout << now.first << " " << now.second << endl;if (now.first == n - 1 && now.second == n - 1)break;now = pre[now.first][now.second];}return 0;
}