AcWing 1112. 迷宫BFS--Java
原题链接
简单
作者:
nq
,
2021-03-14 12:59:12
,
所有人可见
,
阅读 287
import java.io.*;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
public class Main{
static int N = 110;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];
static int n;
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private static boolean bfs(int[] s , int[] e)
{
for(int i = 0 ; i < n ; i ++)Arrays.fill(st[i],false);
if(g[s[0]][s[1]] == '#' || g[e[0]][e[1]] == '#') return false;
if(s[0] == e[0] && s[1] == e[1])return true;
Queue<int[]> q = new LinkedList<>();
q.offer(s);
st[s[0]][s[1]] = true;
while(!q.isEmpty())
{
int dx[] = {0,0,-1,1}, dy[] = {1,-1,0,0};
int[] tmp = q.poll();
for(int i = 0 ; i < 4 ; i ++) {
int x = tmp[0] + dx[i] , y = tmp[1] + dy[i];
if(x < 0 || x >= n || y < 0 || y >= n || st[x][y] == true||g[x][y] == '#') continue;
if(x == e[0] && y == e[1])return true;
st[x][y] = true;
q.offer(new int[] {x,y});
}
}
return false;
}
public static void main(String[] args) throws IOException
{
int k = Integer.parseInt(in.readLine());
while(k -- > 0)
{
n = Integer.parseInt(in.readLine());
for(int i = 0 ; i < n ; i ++)g[i] = in.readLine().toCharArray();
int[] s = new int[2], e = new int[2];
String[] str = in.readLine().split(" ");
s[0] = Integer.parseInt(str[0]);s[1] = Integer.parseInt(str[1]);
e[0] = Integer.parseInt(str[2]);e[1] = Integer.parseInt(str[3]);
boolean ans = bfs(s,e);
if(ans)
System.out.println("YES");
else System.out.println("NO");
}
}
}