【深度优先搜索】是否可通
2024-08-27 09:32:57
发布于:北京
//输入格式
//第一行是两个整数,
//n 和 m(1≤n,m≤40),代表迷宫的长和宽.
//接下来是 𝑛 行,每行 m 个字符,代表整个迷宫。 空地格子用 ‘.’ 表示,有障碍物的格子用 ‘#’ 表示。
//输出格式
//输出能否从左上角走到右下角,如果可以输出 "YES",若走不通,输出 "NO"。输出的内容不包含双引号。
#include<bits/stdc++.h>
using namespace std;
char MAP[49][49];
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool vis[49][49];
int n,m;
bool inmap(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}
bool flag;
void dfs(int x,int y){
if(x==n&&y==m){
flag=true;
return;
}
for(int i=0;i<4;i++){
int nx=x+d[i][0],ny=y+d[i][1];
if(inmap(nx,ny)&&!vis[nx][ny]&&MAP[nx][ny]!='#'){
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>>MAP[i][j];
}}
vis[1][1]=1;
dfs(1,1);
if(flag){cout<<"YES";}
else{cout<<"NO";}
return 0;
}
这里空空如也
有帮助,赞一个