Acwing.提高课.迷宫问题(c++题解)

给定一个 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>
#define xx first
#define yy second
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;int n;
bool G[N][N];
bool f[N][N];int fx[] = {0, 0, 1, -1};
int fy[] = {1, -1, 0, 0};void bfs(int x, int y, int q, int p){PII pre[N][N];queue<PII> Q;Q.push({x, y});pre[x][y] = {x - 1, y - 1};f[x][y] = true;while(!Q.empty()){auto t = Q.front();Q.pop();if(t.xx == q && t.yy == p)break;for(int i = 0; i < 4; i ++){int dx = t.xx + fx[i];int dy = t.yy + fy[i];if(dx < 1 || dy < 1 || dx > n || dy > n)continue;if(f[dx][dy])continue;if(G[dx][dy])continue;Q.push({dx, dy});f[dx][dy] = true;pre[dx][dy] = t;}}stack<PII> st;PII t = {q, p};while(pre[t.xx][t.yy] != t){st.push({t});t = pre[t.xx][t.yy];}while(!st.empty()){t = st.top();st.pop();cout << t.xx - 1 << " " << t.yy - 1 <<"\n";//本题从(0,0)开始}
}int main(){cin >> n;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)cin >> G[i][j];bfs(1, 1, n, n);
}