Jack's Blog

流淌的心,怎能阻拦,吹来的风,又怎能阻挡。

迷宫问题广度搜索--ACM第五讲

Jacob posted @ Oct 30, 2017 08:45:07 PM in C语言 with tags acm , 269 阅读

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)

 

迷宫可以以二维数组来存储表示。0表示通路,1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示,均从0开始,给定起点(0,0)和终点(4,4),迷宫表示如下:

左图每个方块表示一个状态,浅蓝色的表示遍历了该状态。

广度优先搜索即是按层数一层一层来遍历,先将一层全部扩展,然后再进行下一层。

利用队列先进先出(FIFO)的性质恰好可以来完成这个任务

 

对应的队列的情况:

具体过程:

1 每次取出队列首元素(初始状态),进行拓展

2 然后把拓展所得到的可行状态都放到队列里面

3 将初始状态删除

4 循环执行以上三步直到找到目标状态或者队列为空。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
int mp[10][10];
bool inq[10][10];//passed set true

struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y) {}
};
queue<node> q;
node frm[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool bfs(){
    q.push(node(1,1));
    inq[1][1]=true;
    frm[1][1]=node(0,0);
    while (!q.empty()){
        node now = q.front();
        q.pop();
        if (now.x==5 && now.y==5){
            return true;
        }
        for(int i=0;i<4;i++){
            int tx=now.x+dx[i],ty=now.y+dy[i];
            if (!inq[tx][ty] && mp[tx][ty]==0){
                inq[tx][ty]=true;
                q.push(node(tx,ty));
                frm[tx][ty]=now;
            }
        }
    }
    return false;
}
void printans(int x,int y){
    if (x==0 && y==0)   return;
    printans(frm[x][y].x,frm[x][y].y);
    printf("(%d, %d)\n",x-1,y-1);
}
int main(){
    for (int i=0;i<=6;i++){
        for (int j=0;j<=6;j++){
            mp[i][j]=-1;
        }
    }
    for (int i=1;i<=5;i++){
        for (int j=1;j<=5;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    bfs();
    printans(5,5);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter