En una cuadrícula de 10^6 x 10^6, las coordenadas de cada bloque de cuadrícula son (x, y), donde 0 <= x, y <10^6.
Partimos de la cuadrícula de origen y tenemos la intención de apresurarnos a la cuadrícula de destino. Cada vez que nos movemos, podemos caminar hasta el cuadrado adyacente en la cuadrícula en cuatro direcciones, siempre y cuando el cuadrado no esté en la lista de bloques dada.
Solo devuelve true cuando se puede alcanzar el cuadrado objetivo a través de una serie de movimientos. De lo contrario, devuelve false.
Ejemplo 1:
Entrada: bloqueada = [[0,1],[1,0]], fuente = [0,0], objetivo = [0,2]
Salida: false
Explicación:
No se puede alcanzar el cuadrado objetivo desde el cuadrado de origen porque no podemos movernos en la cuadrícula.
Ejemplo 2:
Entrada: bloqueada = [], fuente = [0,0], objetivo = [999999,999999]
Salida: verdadera
Explicación:
Debido a que ningún cuadrado está bloqueado, debe ser capaz de alcanzar el cuadrado objetivo.
Pronto:
0 <= blocked.length <= 200
Bloqueado[i].length == 2
0 <= bloqueado[i][j] < 10^6
source.length == target.length == 2
0 <= fuente[i][j]Objetivo[i][j] < 10^6
fuente != objetivo
Idea: Debido a la gran área del gráfico de cuadrícula, si nos movemos ciegamente hacia la respuesta, definitivamente se agota el tiempo de espera, y observamos que la matriz bloqueada es de sólo 200 en tamaño, por lo que el área que puede cubrir es limitada, por lo que todavía podemos utilizar el método general BFS, pero tenemos que permitir que salga temprano, y después del análisis , podemos saber que cuando el número de movimientos supera unas 20.000 veces, se puede demostrar que debe ser capaz de alcanzar el objetivo a través de un camino (en otras palabras, no está cubierto), y aunque el punto de partida no se puede cubrir, el punto final puede ser cubierto, por lo que necesitamos ver el punto final como el punto de partida y hacerlo de nuevo.
class Solution {
private int num;
private boolean flag;
private int[] dx = new int[]{0, 0, 1, -1};
private int[] dy = new int[]{1, -1, 0, 0};
private Map<String, Boolean> map;
private Map<String, Boolean> vised;
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
map = new HashMap<>();
int len = blocked.length;
for (int i = 0; i < len; i++) {
String s = String.valueOf(blocked[i][0]) + "#" + String.valueOf(blocked[i][1]);
map.put(s, true);
}
return jud(blocked, source, target) && jud(blocked, target, source);
}
private boolean jud(int[][] blocked, int[] source, int[] target) {
num = 0;
flag = false;
vised = new HashMap<>();
bfs(source[0], source[1], target[0], target[1]);
return flag;
}
private void bfs(int x, int y, int target_x, int target_y) {
Queue<int[]> q = new LinkedList<>();
num = 1;
q.add(new int[]{x, y});
String s = String.valueOf(x) + "#" + String.valueOf(y);
vised.put(s, true);
while (!q.isEmpty()) {
int[] now = q.poll();
if (now[0] == target_x && now[1] == target_y) {
flag = true;
return;
}
for (int i = 0; i < 4; i++) {
int xx = now[0] + dx[i];
int yy = now[1] + dy[i];
String ss = String.valueOf(xx) + "#" + String.valueOf(yy);
if (xx < 0 || yy < 0 || check(xx, yy) || vised.containsKey(ss))
continue;
num++;
if (num >= 20000) {
flag = true;
return;
}
q.add(new int[]{xx, yy});
vised.put(ss, true);
}
}
}
private boolean check(int x, int y) {
String s = String.valueOf(x) + "#" + String.valueOf(y);
return map.containsKey(s);
}
}.
