DFS之连通性模型1:1112
作者:
总打瞌睡的天天啊
,
2024-10-21 18:56:38
,
所有人可见
,
阅读 3
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
char g[N][N];
bool st[N][N];
int x1,y1,x2,y2;
int n;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int dfs(int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2)return 1;
for(int i=0;i<4;i++)
{
int wx=x1+dx[i],wy=y1+dy[i];
if(wx<0||wy<0||wx>=n||wy>=n||g[wx][wy]=='#'||st[wx][wy])continue;
if(st[wx][wy])continue;
st[wx][wy]=1;
if(dfs(wx,wy,x2,y2))return 1;
}
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<n;i++)cin>>g[i];
cin>>x1>>y1>>x2>>y2;
if(g[x1][y1]=='#'||g[x2][y2]=='#')
{
printf("NO\n");
continue;
}
if(x1==x2&&y1==y2)
{
printf("YES\n");
continue;
}
st[x1][y1]=1;
int t=dfs(x1,y1,x2,y2);
if(t)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
st[i][j]=false;
}
}
}
return 0;
}