POJ 3984 迷宫问题[BFS]

算法

字数统计: 722阅读时长: 3 min

 2018/10/28   Share

定义一个二维数组：

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

此题题意比较简单，就是找一条左上到右下的最短路，并打印出来。这种简单的最短路直接 $BFS$ 就解决了。稍微麻烦一点在于打印，那么该如何去储存这条最短路线呢？题目明确指出打印出坐标，那直接用个 $pair$ 储存一下 $x,\ y$ 就好了，可以尝试建立一个 $pair$ 数组，又需要路线，那我们存一下前驱坐标就行了。问题来了，从哪端开始存方便一些，如果从起始坐标 $(0,\ 0)$ 处就存的话，结点必然不唯一，比如说离 $(0, \ 0)$ 距离为 $1$ 的可能就好几个（ps：此处不理解的话可以去看看 floodfill）。所以尝试一下从结尾处开始存，结尾处的结点前驱就唯一了，想一想为什么？然而从结尾开始存的话又需要一个栈倒一下顺序，那直接从 $(4,\ 4)$ 向 $(0,\ 0)$搜索就好了。

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b);++i)

bool mm[6][6];
pair<int,int> pre[5][5];

void bfs(int x, int y) {
    queue<pair<int, int> > qq; qq.push(mp(x, y));
    while(!qq.empty()) {
        int inext[] = {0, 0, -1, 1};
        int jnext[] = {-1, 1, 0, 0};
        rep(k, 0, 4) {  // 结点的上下左右各查找一次
            int icur = qq.front().fi + inext[k];
            int jcur = qq.front().se + jnext[k];
            if(icur < 0 || icur >4 || jcur < 0 ||  // 去除越界位置
               jcur > 4 || (icur == x && jcur == y)) continue;
            if(!mm[icur][jcur] && !pre[icur][jcur].first) {  // 能走并且未走过(pair元素默认为空)
                qq.push(mp(icur, jcur));  // 加入队列
                // 此时的队首元素即为下一个结点的前驱，不熟悉的朋友可以建立如下结构，熟悉一下BFS，打印出来观察一下
                // fg[icur][jcur] = fg[qq.front().first][qq.front().second] + 1; 
                // fg[i][j]：i, j位置离起点的最短距离
                pre[icur][jcur] = qq.front();   // 记录前驱位置
            }
            if(icur == 0 && jcur == 0) return;  // 到终点了就退出
        }
        qq.pop();  // 查找过的结点就直接pop
    }
}

int main() {
    //freopen("D:\\i.txt","r",stdin);
    rep(i, 0, 5) rep(j, 0, 5) cin>>mm[i][j];
 
    bfs(4, 4);
    
    puts("(0, 0)");
    pair<int, int> tmp(0, 0);
    while(tmp.fi != 4 || tmp.se != 4) {
        int i = tmp.fi;
        int j = tmp.se;
        pf("(%d, %d)\n", pre[i][j].fi, pre[i][j].se);
        tmp = pre[i][j];
    }
    return 0;
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2018/10/28/POJ-3984-迷宫问题-BFS/

发表日期：October 28th 2018, 1:10:37 pm

更新日期：May 15th 2021, 11:53:20 am

Next Post

POJ 1321 棋盘问题[DFS]
Previous Post

Raccoon web Writeup

CATALOG

