1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| class Solution { int EDGE = (int) 1e6, MAX; Set<Long> set = new HashSet<>(); int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) { for (int[] b : blocked) set.add(b[0] * (long) 1e6 + b[1]); int n = blocked.length; MAX = n * (n - 1) / 2; return bfs(source, target) && bfs(target, source); }
private boolean bfs(int[] source, int[] target) { Set<Long> visited = new HashSet<>(); Deque<int[]> queue = new ArrayDeque<>(); queue.offer(source); visited.add(source[0] * (long) 1e6 + source[1]); while (!queue.isEmpty() && visited.size() <= MAX) { int[] cur = queue.poll(); int x = cur[0], y = cur[1]; if (x == target[0] && y == target[1]) return true; for (int[] dir : dirs) { int nx = x + dir[0], ny = y + dir[1]; if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue; long hash = nx * (long) 1e6 + ny; if (set.contains(hash)) continue; if (visited.contains(hash)) continue; queue.offer(new int[]{nx, ny}); visited.add(hash); } } return visited.size() > MAX; } }
|