AcWing 1112. 迷宫
原题链接
简单
作者:
哈基咪
,
2020-09-16 21:35:08
,
所有人可见
,
阅读 414
//迷宫
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
char map[N][N];
int st[N][N],k,n,ha,la,hb,lb;
bool flag=false;
//定义方向向量
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x, int y)
{
if(x==hb&&y==lb)
{
return true;
}
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<n&&b>=0&&b<n)
{
if(!st[a][b]&&map[a][b]=='.')
{
st[a][b]=1;
if(dfs(a,b)) return true;
}
}
}
return false;
}
int main()
{
cin>>k;
while(k--)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>map[i];
cin>>ha>>la>>hb>>lb;
if(map[ha][la]=='#'||map[hb][lb]=='#')
{
cout<<"NO"<<endl;
continue;
}
memset(st,0,sizeof(st));
if(dfs(ha,la))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}