宽度优先搜索遍历算法-8.4迷宫问题

怼烎@ 2023-07-06 13:19 5阅读 0赞

例8.4迷宫问题
    如图所示，给出一个n*m的迷宫图和一个入口、一个出口
    编写一个程序，打印从一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），白色表示可以走（用0表示）
    只能往上、下、左、右四个方向走。如果无路则输出“no way"
    
    算法分析：
    只要输出一条路径即可，所以是一个经典的回溯算法问题
    和之前的最少步数很类似，都是通过判断四个方向是否可走， 不过不同的是这一题是被动选择下一步，而之前的题目是主动选择然后筛选

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    int u[5]={0,0,1,0,-1};
    int w[5]={0,1,0,-1,0};
    //desx和desy组成出口的坐标
    //soux和souy组成入口的坐标
    //head和tail分别为存储队列的首尾
    int n,m,desx,desy,soux,souy,head,tail,x,y;
    //a,b数组分别用于存放x,y移动的坐标
    //map数组用于存放初始时的 数据，即未开始之前的每个点的值
    //pre数组用于记录父节点，便于打印路径
    int a[51],b[51],pre[51],mmap[51][51];
    bool f;
    
    void print(int d){
        if(pre[d]!=0){
            print(pre[d]);//递归输出路径
        }
        cout<<a[d]<<","<<b[d]<<endl;
    }
    
    //主函数
    int main(){
        //初始化数据
        int i,j;
        //读入迷宫的行数n和列数m
        cin>>n>>m;
        //读入迷宫，0表示通，-1表示不通
        for(i=1;i<=n;i++){
            for (j =1; j <= m; ++j) {
                cin>>mmap[i][j];
            }
        }
        //读入入口的坐标
        cin>>soux>>souy;
        //读入入口的坐标
        cin>>desx>>desy;
        //初始化队列的首尾
        head=0;
        tail=1;
        f=0;
        mmap[soux][souy]=-1;
        a[tail]=soux;
        b[tail]=souy;
        pre[tail]=0;
    
        //处理数据
        //队列不为空的情况下
        while(head!=tail){
            //队首向后移动一位
            head++;
            //总共是四个方向,寻找下一步的可行坐标，即通过加减进行左右移动
            for (i = 1; i <=4 ; ++i) {
                x=a[head]+u[i];
                y=b[head]+w[i];
                //判断上一步得出的x,y坐标是否可以进行
                //即先判断坐标是否在迷宫内，然后判断是否可行
                if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(mmap[x][y]==0)){
                    //下一步可行，将得到的坐标追加到队尾
                    tail++;
                    a[tail]=x;
                    b[tail]=y;
                    pre[tail]=head;
                    //走过的位置做个标记
                    mmap[x][y]=-1;
                    //判断扩展出的节点是否为目标节点
                    if((x==desx)&&(y==desy)){
                        f=1;
                        print(tail);
                        break;
                    }
                }
            }
            //找到目标节点
            if(f){
                break;
            }
        }
        //如果遍历完所有没有找到出口，则失败
        if(!f){
            cout<<"no way."<<endl;
            return 0;
        }
    }

总结：

1.这一题要输出走迷宫的路径，所以要比之前的题目多设置一个pre数组，用于记录走过的点

2.在使用递归方法打印的时候，注意将cout语句放在if语句外面，因为初始化数据的时候pre\[tail\]=0,

所以如果放在里面会漏掉迷宫入口的坐标

3.广度优先搜索算法大致可以概括成三个步骤：

（1）确定下一步应该怎样走，也就是计算下一步的坐标

（2）判断得出的坐标是否满足条件，也就是判断是否越界和可行

（3）移动位置的同时更新队列中的坐标，也就是将移动的坐标保存在一个队列中