首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BFS算法入门--POJ3984

BFS算法入门--POJ3984

作者头像
Enterprise_
发布2019-02-21 17:29:51
4480
发布2019-02-21 17:29:51
举报
文章被收录于专栏:小L的魔法馆小L的魔法馆

迷宫问题–POJ3984 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22008 Accepted: 12848 Description

定义一个二维数组:

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

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 Sample Output

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

CE–4次,PE–2次.

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>


#define N 5                 //迷宫长度
#define M 5                 //迷宫宽度
using namespace std;
int maze[N][M];

typedef struct point
{
    int x;
    int y;
    point *previous;
    int step;
}point;
int sx = 0, sy = 0;         //起点
int gx = 4, gy = 4;         //终点
int dir[4][2] = {           //方向
    {0,1},{1,0},            //上,右
    {0,-1},{-1,0}           //下,左
};


void show(point *p)         //逆向输出链表
{
    if (p != NULL)
    {
        show(p->previous);
        cout << "(" << p->x << ", " << p->y << ")" << endl;
    }
}

void BFS(point start)
{
    queue<point> q;
    q.push(start);               //把头节点放入队列
    point current,next;

    while (!q.empty())
    {
        current = q.front();     // 记录当前节点
        q.pop();                 //弹出元素
        maze[current.x][current.y] =1;

        for (int i = 0; i < 4; i++)
        {
            /*此处本来可以使用next{ current.x + dir[i][0],current.y + dir[i][1],NULL,0 };这样的写法,但是poj不认,所以退而求其次,用下面这种写法*/
            next.x=current.x + dir[i][0];        
            next.y=current.y + dir[i][1];
            next.previous=NULL;
            next.step=0 ;
            if (next.x >= 0 && next.x < N&&next.y >= 0 && next.y < M&&maze[next.x][next.y] ==0)                //判断这个点是否合乎要求,即在迷宫数组内,但是又不是墙,并且没有被标记过
            {
                point *tmp = new point;                         //申请空间
                memcpy(tmp, &current, sizeof(point));           //复制地址
                next.previous = tmp;
                //next.step = current.step + 1;                //如果需要记录路径的话,就加上这一句
                maze[next.x][next.y] = 1;                      //表示这个点已经被搜索过了,所以标记
                    if (next.x == gx &&next.y==gy)//如果发现到了终点,那么就输出路径
                {
                    show(&next);
                    return;
                }
                q.push(next);          //将下一个点加入队列
            }
        }
    }
}


int main(void)
{
    for (int i = 0; i <= 4; ++i)
        for (int j = 0; j <= 4; ++j)
            cin >> maze[i][j];

    point start;
    start.x=0;
    start.y=0,start.previous=NULL;
    start.step=0;
    BFS(start);
    return 0;
}
这里主要是记录路径比较麻烦,如果不考虑这个,就是一道简单的BFS题,对于BFS,需要将题目抽象成一副图,包含对应的节点和对应的边,在这里,节点就是迷宫的每个点,如果两个点之间是联通的话,那么可以认为两个节点之间建立了一条边,而对于迷宫而言,就是一个无权图,或者说是个权重为1的有权图,通过广搜就可以获得起路径,而BFS是否一定会获得最短路径,这个是一定的。
http://blog.csdn.net/raphealguo/article/details/7523411
这个作者讲的很清楚,我也是从中得到启发。
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年06月22日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档