题目描述

给定一个 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

C++ 代码

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int ,int> PII;
const int N = 1010;
PII from[N][N];  // 记录站在当前位置是从自何处走来
int g[N][N], visited[N][N]; // 地图数组，访问数组
// 在迷宫问题和走迷宫两题中，当前能站的位置的坐标一定是合法的。因为起点是合法的，
// 即不是在迷宫外部也不站在是墙的位置处。下一步的位置是否合法，咱还不知道。所以，判断在for循环中出现。
// 机器人移动的范围一题中，每个位置都要检测合法性。最开始站在起点合不合法咱还不知道呢？
// 合不合法就必须要判断。所以在此题中判断就放在了(1)中专门来判断当前位置是否合法。
//至于下一个位置合不合法，会在循环的下轮中来判断
void bfs(int n) {
    queue <PII> q;
    q.push({0, 0});
    int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
    while(!q.empty()) {
        // (1)
        auto t = q.front();  // t是当前位置
        q.pop();
        // (1)   此段是当前站在的位置的坐标
        for(int i = 0; i < 4; i++) {
        // (2)
            int x = t.first + dx[i], y = t.second + dy[i]; // 下一个位置的坐标(x, y)
            if(x < 0 || x > n - 1 || y < 0 || y > n - 1) continue; // 下一个位置越界
            if(g[x][y] || visited[x][y]) continue; // 下一个位置是墙或者已经被访问过
            visited[x][y] = 1; // (x,y)未被访问过，访问标记为1
            from[x][y] = t; // 记录走到(x,y)相邻的上一个位置
            q.push({x, y}); // (x, y)入队列
        // (2) 下一个位置的坐标，能否站上去得看该位置的坐标是否合法
        }
    }
}

void print(int n) {
    stack<PII> s;
    int x = n - 1; // 出口位置 
    int y = n - 1;
    while(x || y) {  // 显然排除了入口
        s.push({x, y});  // 合法位置入栈
        auto t = from[x][y]; // 得到走到(x,y)相邻的上一个位置
        x = t.first, y = t.second;
    }

    s.push({0, 0}); // 起点入栈 
    while(!s.empty()) { // 栈非空代表还没输完
        cout << s.top().first << ' ' << s.top().second << endl;
        s.pop(); // 输出后，无效数据出栈
    }
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) // 输入迷宫
        for(int j = 0; j < n; j++) cin >> g[i][j];
    bfs(n);
    print(n);
    return 0;
}