AcWing 1112. 迷宫
原题链接
简单
作者:
hai阿卢
,
2021-03-11 21:20:59
,
所有人可见
,
阅读 308
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
char a[N][N];
bool s[N][N];
int n;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool dfs(int a1, int a2, int b1, int b2)
{
int x = a1, y = a2;
if(x == b1 && y == b2) return true;
s[x][y] = true;
for(int i = 0; i < 4; i++)
{
int xi = x + dx[i];
int yi = y + dy[i];
if(yi >= 0 && yi < n && xi >= 0 && xi < n && !s[xi][yi] && a[xi][yi] == '.')
{
if(dfs(xi, yi, b1, b2)) return true;
}
}
return false;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
int a1, a2, b1, b2;
cin >> a1 >> a2 >> b1 >> b2;
memset(s, 0, sizeof(s));
if(a[a1][a2] == '#' || a[b1][b2] == '#')
{
cout << "NO" << endl;
continue;
}
if(dfs(a1, a2, b1, b2)) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}