侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【BFS】迷宫问题

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 260 阅读 / 590 字
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1076. 迷宫问题


给定一个 n×nn \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。

接下来 nn 行,每行包含 nn 个整数 0 或 1,表示迷宫。

输出格式

输出从左上角到右下角的最短路线,如果答案不唯一,输出任意一条路径均可。

按顺序,每行输出一个路径中经过的单元格的坐标,左上角坐标为 (0,0)(0,0) ,右下角坐标为 (n1,n1)(n-1,n-1)

数据范围

0n10000 \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;
}
0

评论区