- C++
-TJ 20250119
- 2025-1-19 8:57:46 @
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 105;
int n, f;
char a[N][N];
int sx, sy, ex, ey;// startx endx
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int vis[N][N];
struct Point
{
int x, y;
};
void bfs()
{
queue<Point> mq;
mq.push({sx, sy});
while(mq.size())
{
Point p = mq.front();mq.pop();
if(p.x == ex && p.y == ey)
{
f = 1;
return;
}
for(int i = 0; i < 4; i++)
{
int cx = p.x + dx[i], cy = p.y + dy[i];
if(cx < 1||cx > n || cy < 1||cy > n) continue;
if(a[cx][cy] == '#') continue;
if(vis[cx][cy]) continue;
vis[cx][cy] = 1;
mq.push((Point){cx, cy});
}
}
}
void dfs(int x, int y)
{
if(f == 1) return;
if(x == ex && y == ey)
{
f = 1;
return;
}
for(int i = 0; i < 4; i ++)
{
int cx = x + dx[i], cy = y + dy[i];
if(cx < 1||cx > n || cy < 1||cy > n) continue;
if(a[cx][cy] == '#') continue;
if(vis[cx][cy]) continue;
vis[cx][cy] = 1;
dfs(cx, cy);
vis[cx][cy] = 0;
}
}
int main(void)
{
ios::sync_with_stdio(0);
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i = 1; i <=n; i ++) cin >> (a[i] + 1);
cin >> sx >> sy >> ex >> ey;sx++,sy++,ex++,ey++;
f = 0;
memset(vis, 0, sizeof 0);
vis[sx][sy] =1;
if(a[sx][sy] == '#' || a[ex][ey] == '#')
{
cout << "NO"<< endl;
continue;
}
//dfs(sx, sy);
bfs();
cout << (f == 1 ? "YES" : "NO") << endl;
}
return 0;
}
0 条评论
目前还没有评论...