题解-29783.迷宫1

本题主要考察dfs(深度优先搜索)

*题目解析
题目给出一个只能上下左右走的字符迷宫,
迷宫的长和宽(n,m),要求走出迷宫的可行度
其中字符'.'表示可行走的路,'X'表示不可走的
墙,'S'和'T'分别表示迷宫的起点和终点.
——————————————————————
*代码思路
这里所需变量比较多:设定两个bool类的值
(变量f,数组vis),f表示是否走出迷宫,vis则是
储存迷宫每个点能不能走(能走为true,反之false).
int类型的n,m,sx,sy,ex,ey.(sx,sy表示迷宫起点'S')
(ex,ey表示迷宫终点'T').还有一个储存迷宫的字符数组a.
先输入n,m,字符迷宫,判断出起和终点后放入dfs函数里
进行深度优先搜索.若找到路线(f=1)输出YES,反之则
输出NO.最后还有两个方向数组,表示每一步可动的xy轴.
——————————————————————
*代码展示

#include<bits/stdc++.h>//定义头文件
using namespace std;//用户命名空间
int n,m;//定义全局变量n,m
bool vis[30][30];//vis二维存储数组
bool f=0;//能否通过
char a[30][30];//存储迷宫
int xx[4]={0,0,1,-1};//每一步可动的x轴
int yy[4]={1,-1,0,0};//每一步可动的y轴
int sx,sy,ex,ey;//定义起点和终点
void dfs(int x,int y){//dfs函数
    if(x==ex&&y==ey){//若到达终点,f=1,退出函数;
        f=1;
        return;
    }
    for(int i=0;i<4;i++){//对四个方向进行遍历
        int nx=xx[i]+x;//求出新的xy轴
        int ny=yy[i]+y;
        if(nx>=1 && ny>=1 && nx<=n && ny<=m && vis[nx][ny]==0 && a[nx][ny]!='X'){//如果符合条件(没有超界、没有走过等)
            vis[nx][ny]=1;//把vis标记为1,表示走过
            dfs(nx,ny);//递归,表示下一步新的起点
            vis[nx][ny]=0;//回溯操作
        }
    }
}
int main(){//主函数
    cin>>n>>m;//输入n和m
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){//输入迷宫
            cin>>a[i][j];
            if(a[i][j]=='S'){//去找终点和起点
                sx=i,sy=j;
            }
            if(a[i][j]=='T'){
                ex=i,ey=j;
            }
        }
    }
    vis[sx][sy]=1;//标记起点
    dfs(sx,sy);//调用函数
    if(f){//如果能走到
        cout<<"YES";//输出YES
    }
    else{
        cout<<"NO";//不能则输出NO
    }
    return 0;//完美结束(*^▽^*)
}

*后记
求求给个赞吧qwq