dfs深搜模板
2024-07-28 09:12:28
发布于：上海
24阅读
0回复
0点赞
//深搜模板
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,x,y;
bool flag;
char mp[100][100];
int vis[100][100];
bool inmap(int x,int y) {
return x>=1&&x<=n&&y>=1&&y<=m;
}
//调用dfs深搜
void dfs(int x,int y) {
//判断重点
if (x==n&&y==m) {
flag=1;
return ;
}
if (flag==1) return ;
//判断是否访问过
vis[x][y]=1;
//向四个方向搜索
//开始深搜
//i从0开始
for (int i=0;i<4;i++) {
int nx=x+dir[i][0];
int ny=y+dir[i][1];
//判断是否在地图内,是否访问过，是否有障碍
if (inmap(nx,ny)&&mp[nx][ny] !='#'&&vis[nx][ny]==0) {
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];
dfs(1,1);
if(flag==1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
有帮助，赞一个