POJ 3984 迷宫问题最短路径求解

基于广度优先搜索（BFS）算法解决 5x5 迷宫最短路径问题。输入为表示墙壁与通路的二维数组，输出从左上角至右下角的坐标序列。程序通过队列管理节点遍历，利用父节点记录路径并回溯打印结果。代码修正了方向循环范围及访问标记逻辑以确保正确性。

RustyLab发布于 2017/11/40 浏览

题目描述

定义一个二维数组：

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 表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个 5 × 5 的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

参考代码

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 10;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int maze[maxn][maxn];
bool vis[maxn][maxn];
struct node {
    int x;
    int y;
} befo[maxn][maxn];

void print(node a) {
    vector<node> nodes;
    for (;;) {
        nodes.push_back(a);
        if (a.x == 0 && a.y == 0) break;
        a = befo[a.x][a.y];
    }
    for (int i = nodes.size() - 1; i >= 0; i--) {
        cout << "(" << nodes[i].x << ", " << nodes[i].y << ")" << endl;
    }
}

void bfs() {
    queue<node> q;
    node pre, nxt;
    pre.x = 0, pre.y = 0;
    q.push(pre);
    vis[0][0] = true;
    while (!q.empty()) {
        pre = q.front();
        
        if (pre.x == 4 && pre.y == 4) {
            print(pre);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int tempx = pre.x + dir[i][0];
            int tempy = pre.y + dir[i][1];
            if (tempx >= 0 && tempx <= 4 && tempy >= 0 && tempy <= 4 && maze[tempx][tempy] == 0 && !vis[tempx][tempy]) {
                nxt.x = tempx;
                nxt.y = tempy;
                q.push(nxt);
                vis[tempx][tempy] = true;
                befo[tempx][tempy] = pre;
            }
        }
        q.pop();
    }
}

int main() {
    ios::sync_with_stdio(false);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) cin >> maze[i][j];
    bfs();
    return 0;
}