迷宫--广度优先搜索

Love The Way You Lie 2022-06-02 06:50 219阅读 0赞

*  对于上一个迷宫的问题也可使用广度优先搜索（Breadth First Search，BFS），也称作宽度优先搜索。
 *  深度优先搜索的方法是一直搜索下去，直到走不通，再回到原地。而广度优先搜索是是“一层一层”的扩展进行搜索。最开始假设还是（1，1）处，一步可以到达的点有（1，2）和（2，1）  
    ![22069477.jpg][]
 *  但是还没有找到目标，继续通过这两个（1，2）、（2，1）点往下走。之后，他能走到哪个点呢？（2，2），通过（2，1）还可以到（3，1），并且都是用2步，这里依然需要使用数组进行标记这个点是否走过。  
    ![33716812.jpg][]
 *  然后依次类推继续搜索；
 *  在上面的过程中，需要使用个结构体实现队列，

struct note{ 
    	  int x;
    	  int y;
    	  int s;//记录步数 
    }

![11804750.jpg][]

*  从（1，1）开始，先尝试往右走到了（1，2），对其进行判断是否越界或为障碍物或已经走过（使用前边介绍的book数组标记）。  
    ![1655021.jpg][]  
    \-从（1，1）也可以到达（2，1）。  
    ![53943356.jpg][]
 *  出队时使用head++就可以啦！；  
    ![4784160.jpg][]
 *  代码：

#include<iostream>
    using namespace std;
    int next[4][2]={ { 0,1},{ 1,0},{ 0,-1},{ -1,0}};
    struct note{ 
        int x;
        int y;
        int f;
        int s;
    };
    int main(){ 
    struct note que[2501];
        int head,tail;
         int sx,sy,tx,ty,q,p,m,n,flag;
        int a[51][51]={ 0};
        int book[51][51]={ 0};
        cin>>n>>m;
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                cin>>a[i][j];
            }
        }
        cin>>sx>>sy>>p>>q;
        head=1;
        tail=1;
        que[tail].x=1;
        que[tail].y=1;
        que[tail].s=0;
        tail++;
        book[sx][sy]=1;
        flag=0;
        while(head<tail){ 
            for(int k=0;k<=3;k++){ 
                tx=que[head].x+next[k][0];
                ty=que[head].y+next[k][1];
                if(tx<1||ty<1||tx>n||ty>m)
                    continue;
                if(a[tx][ty]==0&&book[tx][ty]==0){ 
                    book[tx][ty]=1;
                    que[tail].x=tx;
                    que[tail].y=ty;
                    que[tail].f=head;
                    que[tail].s=que[head].s+1;
                    tail++;
                }
                if(tx==p&&ty==q){ 
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
            head++;
        }
        cout<<que[tail-1].s<<endl;
        return 0;
    }

*  测试数据：

5  4
     0   0    1   0
     0   0    0   0
     0   0    1   0 
     0   1    0   0
     0   0    0   1
     1   1    4   3

*  运行结果：

> 7

[22069477.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/22069477.jpg
[33716812.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/33716812.jpg
[11804750.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/11804750.jpg
[1655021.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/1655021.jpg
[53943356.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/53943356.jpg
[4784160.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/4784160.jpg