【BFS】迷宫问题

题目

1076. 迷宫问题

---

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

解题

方法一：BFS

思路

宽搜并记录路径，搜到终点后倒序输出路径即可。

代码

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

const int N = 1010, M = N * N, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, g[N][N], prevs[M];

void bfs() {
    queue<int> que;
    que.push(0);
    g[0][0] = 1;
    while (!que.empty()) {
        int curr = que.front();
        que.pop();
        int x = curr / n, y = curr % n;
        if (x == n - 1 && y == n - 1) {
            stack<int> path;
            for (int i = (n - 1) * n + n - 1; i; i = prevs[i]) path.push(i);
            puts("0 0");
            while (!path.empty()) {
                int coord = path.top();
                path.pop();
                printf("%d %d\n", coord / n, coord % n);
            }
            return;
        }
        for (auto& DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !g[nx][ny]) {
                que.push(nx * n + ny);
                g[nx][ny] = 1;
                prevs[nx * n + ny] = curr;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) scanf("%d", &g[i][j]);
    }
    bfs();

    return 0;
}