Jack's Blog

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

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

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

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(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;
}
Avatar_small
黑道風雲 说:
2018年9月11日 15:46

我一直很想学代码编程,感觉很牛逼!

Avatar_small
Jacob 说:
2018年11月07日 15:41

@黑道風雲: 朋友加油!

Avatar_small
IndusInd bank net ba 说:
2022年8月07日 15:55

Indusind Bank is quite well known as it provides all essential banking services without much fees that has garnered them a lot of customers across the years. If you are someone who has an IndusInd bank account then you might know how great their service is. IndusInd bank net banking login They provide different banking services from setting up of savings, personal account, providing of loans, credit and debit cards as well. Now with internet banking on the rise, they have made their IndusInd bank login process quite easy. In this article we will help you learn more about it.

Avatar_small
Emma 说:
2023年1月17日 18:25

There are a number of ways to solve a maze problem, but one of the most common is breadth-first search. This real estate price Winfield method involves exploring all of the possible paths from the starting point to the goal, one at a time. If a path leads to the goal, then the problem is solved. Otherwise, the search backtracks and tries another path.


登录 *


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