集训 迷宫题解 深搜做法

鉴于刚学完深搜，来巩固一下。
非常模板的题。（套上模版就好了）
想要完整版代码请划到最下面

我感觉深搜的便利过程，就是枚举，枚举每一种可能，再去进行判断。(深搜就是有亿点点难的枚举）
先分析提意
有一个n行m列的矩阵
要从A(sx,sy)走到 B(fx,fy) 如果可以走到输出”YES“否则输出”NO“
.代表这个格子能走,否则#就不能走到这个格子上。

再来看一下思路

其实就是我们从起点开始一一枚举，然后判断四周收是否能走，是否越出矩阵，这个格子之前是否有被走过。如果有下一步也要这样判断

所以这边需定义几个变量
及定义整型变量的n,m用来存储这个矩阵的大小范围。

定义char类型的二维数组mp用来存下这张地图，在函数内依此来判断是否是障碍物。

还有两个方向数组dx，与dy,这里是为了更方便的去便利这个点的上，下，左，右。当然如果你不嫌麻烦的话可以自己慢慢加，在复制n遍if判断。我的遍历顺序我也是这样写的。dx和dy存的是在判断四周行列坐标的变化，例如当判断上方的点时y坐标要减1，而x坐标不变即0，剩下三个以此类推....这里的遍历可以根据题目做出顺序上的改变，比如让你输出每步怎么走时，你就要按他给的顺序变化这两个数组。八个方向的变化也是以此类推。

这里定义布尔类型的vis成为访问数组，以此来判断这个点是否被走过，被遍历过。我觉得定bool和定int没啥区别

int n,m,sx,sy,fx,fy;
char mp[45][45];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[45][45],flag;

这下面是迷宫函数的写法

void dfs(int sx,int sy){
    if(sx==fx&&sy==fy){//这里是判断如果到达了终点，就要结束了，将flag的结果变为真。
        flag=1;
        return ;
    }
    vis[sx][sy]=1;
    for(int i=0;i<4;i++){
        int nx=sx+dx[i];//变化后的行和列坐标
        int ny=sy+dy[i];
        if(nx>=1&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]!='#'&&!vis[nx][ny]){//判断这里是否能走。
            vis[nx][ny]=1;//标记成真，表示此处被访问过了。 （只要赋值不是0就都是真，我放在了主函数里所以全都初始化为0就是假）
            dfs(nx,ny);//再次判断它的下一步的走法。
        }
    }
}

这就是最基础的输入和输出了。

int main(){
     cin>>n>>m;
    cin>>sx>>sy>>fx>>fy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    dfs(sx,sy);
    if(flag) cout<<"YES";//判断是否达到终点，依题。
    else cout<<"NO";
}

完整代码

#include<iostream>
using namespace std;
int n,m,sx,sy,fx,fy;
char mp[45][45];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[45][45],flag;
void dfs(int sx,int sy){
    if(sx==fx&&sy==fy){
        flag=1;
        return ;
    }
    vis[sx][sy]=1;
    for(int i=0;i<4;i++){
        int nx=sx+dx[i];
        int ny=sy+dy[i];
        if(nx>=1&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]!='#'&&!vis[nx][ny]){
            vis[nx][ny]=1;
            dfs(nx,ny);
        }
    }
}
int main(){
     cin>>n>>m;
    cin>>sx>>sy>>fx>>fy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    vis[sx][sy]=1;//我前面忘写了，不过这个测试样例不影响嘻嘻ヾ(≧▽≦*)o
    dfs(sx,sy);
    if(flag) cout<<"YES";
    else cout<<"NO";
}

这是本人的第一个题解，希望大家能够喜欢。如果有没看懂的地方，可以联系我的哦。（别问我为什么，问就是闲的没事干想找人聊天）
如有字敲错了，或语言术语问题，请多多包涵。
我写了一个多小时的题解 我很认真对待它了 禁止盗走 作者会哭的
记得点赞 关注 加收藏