迷宫--深度优先搜索

迈不过友情╰ 2022-06-02 06:49 202阅读 0赞

*  在迷宫中，有许多路障，如何在最快的时间，也就是路程最短啦,去解救一个人呢？  
    ![25752359.jpg][]
 *  使用一个二维数组来存储这个迷宫，刚开始的时候，小明处于迷宫的入口（1，1）。迷路的瞎子在（p,q）。
 *  同时每次在一个位置都需要对所在的位置对四个方向进行顺序尝试，解决方法是使用一个方向数组next，如下：
    
        int next[4][2]={
            {0,1},{1,0},{0,-1},{-1,0}};
    
    ![26925492.jpg][]
 *  然后使用方向数组，使用循环很容易获得下一步的坐标。这里使用tx存储横坐标，ty存储纵坐标。
    
        for(k=0;k<=3;k++){
        tx=x+next[k][0];
        ty=y+next[k][1];
        }
 *  代码：

#include<iostream>
    using namespace std;
     int mina=0x3fffff;
    int a[100][100],book[100][100],p,q,n,m;
     int next[4][2]={
      {0,1},{1,0},{0,-1},{-1,0}};
     void dfs(int x,int y,int step){
         int tx,ty,k;
        if(x==p&&y==q){
            if(step<mina){
                    mina=step;
                return ;
            }
        }
        for(k=0;k<=3;k++){
            tx=x+next[k][0];
            ty=y+next[k][1];
            if(tx<1||tx>n||ty<1||ty>m)
                continue;
            if(a[tx][ty]==0&&book[tx][ty]==0){
                book[tx][ty]=1;
                dfs(tx,ty,step+1);
                book[tx][ty]=0;
            }
        }
        return ;
     }
    int main(){
       int sx,sy;
       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;
       book[sx][sy]=1;
       dfs(sx,sy,0);
       cout<<mina<<endl;
    }

[25752359.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/25752359.jpg
[26925492.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/26925492.jpg