POJ 3984 迷宫问题[BFS]

admin
admin
admin
138023
文章
113
评论
2024年8月18日00:33:30评论7 views字数 1545阅读5分9秒阅读模式

定义一个二维数组： 

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;
}

FROM:wywwzjj

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年8月18日00:33:30
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   POJ 3984 迷宫问题[BFS]https://cn-sec.com/archives/3075364.html
                  免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉.

发表评论

匿名网友 填写信息