可行路径判断————四班专用
2023-08-17 13:42:14
发布于：浙江
10阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
char a[105][105];
int n,t,sx,sy,fx,fy,vis[105][105],flag;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){
if(flag) return;
if(x==fx && y==fy){
flag=1;
return;
}
for(int i=0;i<4;i++){
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx<0 || xx>=n || yy<0 || yy>=n) continue;
if(a[xx][yy]=='#' || vis[xx][yy]) continue;
vis[xx][yy]=1;
dfs(xx,yy);
}
}
int main(){
cin>>t;
while(t--){
flag=0;
memset(vis,0,sizeof vis);//初始化为0
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
cin>>sx>>sy>>fx>>fy;
if(a[sx][sy]=='#' || a[fx][fy]=='#'){
cout<<"NO\n";
continue;
}
vis[sx][sy]=1;
dfs(sx,sy);
if(!flag) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
有帮助，赞一个