AcWing 1112. 迷宫
原题链接
简单
作者:
Codecat
,
2021-03-10 15:07:59
,
所有人可见
,
阅读 362
#include<iostream>
#include<cstring>
using namespace std;
const int N =120;
char ch[N][N];
int n;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int a1,a2,b1,b2;
bool st[N][N];
bool dfs(int x,int y){
if(x== b1 && y == b2){
return true;
}
st[x][y] = true;
for (int i = 0 ; i < 4 ; i ++){
int kx = x + dx[i];
int ky = y + dy[i];
if(kx >=0 && ky >= 0 && kx< n && ky < n){
if(ch[kx][ky] != '#')
{
if(!st[kx][ky])
{
if(dfs(kx,ky))return true;
}
}
}
}
return false;
}
int main(){
int k ;
cin >> k;
while(k --){
memset(st, false, sizeof(st));
cin >> n;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++){
cin >> ch[i][j];
}
cin >> a1>>a2>>b1>>b2;
if(ch[a1][a2] == '#' || ch[b1][b2] == '#'){
puts("NO");
continue;
}
if(dfs(a1,a2)){
cout<<"YES"<<endl;
}else{
puts("NO");
}
}
return 0;
}