DFS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int k;
int n;
char g[N][N];
bool check;
void dfs(PII start,PII end)
{
int dx[4] = {0 , 1 , 0 , -1},dy[4] = {1 , 0 , -1, 0};
PII t;
g[start.x][start.y] = '#';
for ( int i = 0; i < 4 ; i++)
{
t.x = start.x + dx[i], t.y = start.y + dy[i];
if(t.x >= 0 && t.x <= n && t.y >=0 && t.y <= n && g[t.x][t.y] == '.')
{
if(t.x == end.x && t.y == end.y)
{
check = true;
return;
}
else dfs(t,end);
}
}
return;
}
int main()
{
cin >> k;
while ( k--)
{
//int n;
cin >> n;
for (int i = 0; i < n ; i ++)
for (int j = 0 ; j < n ; j++)
cin >> g[i][j];
PII start,end;
cin >> start.x >> start.y >> end.x >> end.y;
if(start.x == end.x && start.y == end.y && g[end.x][end.y] == '.') cout << "YES" << endl;
else if(g[start.x][start.y] == '#' || g[end.x][end.y] == '#') cout << "NO" << endl;
else
{
check = false;
dfs(start,end);
if(check) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
BFS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int k;
int n;
char g[N][N];
bool check;
void bfs(PII start,PII end)
{
queue<PII> q;
q.push(start);
g[start.x][start.y] = '#';
int dx[4] = {0 , 1 , 0 , -1},dy[4] = {1 , 0 , -1, 0};
while(q.size())
{
PII t = q.front();
q.pop();
for (int i = 0 ; i < 4; i++)
{
int x = t.x + dx[i];
int y = t.y + dy[i];
if(x == end.x && y == end.y)
{
check = true;
break;
}
if (x < 0 || x > n || y < 0 || y > n || g[x][y] == '#') continue;
if (g[x][y] == '.')
{
q.push({x,y});
g[x][y] = '#';
}
}
}
}
int main()
{
cin >> k;
while ( k--)
{
//int n;
cin >> n;
for (int i = 0; i < n ; i ++)
for (int j = 0 ; j < n ; j++)
cin >> g[i][j];
PII start,end;
cin >> start.x >> start.y >> end.x >> end.y;
if(start.x == end.x && start.y == end.y && g[end.x][end.y] == '.') cout << "YES" << endl;
else if(g[start.x][start.y] == '#' || g[end.x][end.y] == '#') cout << "NO" << endl;
else
{
check = false;
bfs(start,end);
if(check) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}