AcWing 1112. 迷宫(dfs)
原题链接
简单
作者:
逸误
,
2024-04-07 20:06:20
,
所有人可见
,
阅读 4
//深搜,搜索连通性
//防止重复走,加一个判重数组st就可以了
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int k,n;
char g[N][N];
bool st[N][N];
int x1,y1,x2,y2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x,int y)
{
st[x][y]=true;//标记走过,下次不会再走
if(x==x2&&y==y2)
return true;
for(int i=0;i<=3;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=n||g[xx][yy]=='#'||st[xx][yy])//越界或者是墙壁或者走过,就不走
continue;
if(dfs(xx,yy))
return true;
}
return false;
}
int main()
{
cin>>k;
while(k--)
{
memset(st,false,sizeof st);//第一次写忘记更新了,每次询问都要先清空状态数组!!!
cin>>n;
for(int i=0;i<n;i++)
{
string str;
cin>>str;
for(int j=0;j<n;j++)
g[i][j]=str[j];
}
cin>>x1>>y1>>x2>>y2;
if(g[x1][y1]=='#'||g[x2][y2]=='#')
{
puts("NO");
continue;
}
if(dfs(x1,y1))
puts("YES");
else
puts("NO");
}
return 0;
}