AcWing 1112. 迷宫
原题链接
简单
作者:
STU756
,
2024-01-01 21:14:28
,
所有人可见
,
阅读 31
import java.util.*;
public class Main{
static final int N = 110;
static int n;
static int ax, ay, bx, by;
static char g[][] = new char[N][N];
static boolean st[][];
static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
static boolean dfs(int x, int y) {
if(g[x][y] == '#') return false;
if(x == bx && y == by) return true;
st[x][y] = true;
for(int i = 0; i < 4; i++){
int a = dx[i] + x, b = dy[i] + y;
if(a < 0 || a >= n || b < 0 || b >= n) continue;
if(st[a][b]) continue;
// if(g[a][b] == '#') continue;
if(dfs(a, b)) {
return true;
}
}
return false;
}
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t -- > 0){
st = new boolean[N][N];
n = s.nextInt();
for(int i = 0; i < n; i++){
String str = s.next();
for(int j = 0; j < n; j++){
g[i][j] = str.charAt(j);
}
}
ax = s.nextInt();
ay = s.nextInt();
bx = s.nextInt();
by = s.nextInt();
if(dfs(ax, ay)) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
}