Day05-深度优先搜索 迷宫
2023-08-16 16:08:56
发布于：浙江
12阅读
0回复
0点赞
#include<iostream>
using namespace std;
int n,m,flag=0;
char mp[45][45];
int dx[4]={0,1,0,-1}; //4个方向x的变化
int dy[4]={1,0,-1,0}; //4个方向y的变化
int vis[45][45];//标记x，y是否走过
void dfs(int x,int y){//x和y表示当前所处的为止
//递归边界 走到终点
if(x==n && y==m){
flag=1;
return; //返回
}
//站在(x,y)的位置
for(int i=0;i<=3;i++){//计算出4个方向的坐标
int nx=x+dx[i],ny=y+dy[i];
//相邻点越界
if(nx<1 || nx>n || ny<1 || ny>m) continue;
if(mp[nx][ny]=='#') continue;
if(vis[nx][ny]==1) continue;
//nx ny ---(n,m)
vis[nx][ny]=1;//标记走过了
dfs(nx,ny);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
//(1,1)------>(5,5)
dfs(1,1);//刚开始从（1，1）走起
//深度优先搜索：depth first search
if(flag==1) cout<<"YES";
else cout<<"NO";
return 0;
}
这里空空如也
有帮助，赞一个