Formatted question description: https://leetcode.ca/all/1036.html
1036. Escape a Large Maze
Level
Hard
Description
In a 1 million by 1 million grid, the coordinates of each grid square are (x, y)
with 0 <= x, y < 10^6
.
We start at the source
square and want to reach the target
square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked
squares.
Return true
if and only if it is possible to reach the target square through a sequence of moves.
Example 1:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation:
The target square is inaccessible starting from the source square, because we can’t walk outside the grid.
Example 2:
Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation:
Because there are no blocked cells, it’s possible to reach the target square.
Note:
0 <= blocked.length <= 200
blocked[i].length == 2
0 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target
Solution
Since the grid is very large, directly using breadth first search is quite time-consuming. One way is to check whether the source is in a closed area and whether the target is in a closed area. Suppose there are m
cells that are blocked. The maximum possible closed area is m * (m - 1) / 2
.
Do breadth first search for two times. The first time search from source
to target
. If target
can be reached, then return true
without the second search. If at one step, the number of visited cells is greater than m * (m - 1) / 2
, then the second search is required. Otherwise, return false
without the second search.
The second time search from target
to source
. If at one step, the number of visited cells is greater than m * (m - 1) / 2
, then return true
. Otherwise, return false
.
class Solution {
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked == null || blocked.length == 0)
return true;
final int MAX = 1000000;
Set<String> blockedSet = new HashSet<String>();
int blockedSize = blocked.length;
for (int i = 0; i < blockedSize; i++)
blockedSet.add(Arrays.toString(blocked[i]));
int search1 = breadthFirstSearch(MAX, blockedSet, source, target);
if (search1 == 2)
return true;
else if (search1 == 0)
return false;
else {
int search2 = breadthFirstSearch(MAX, blockedSet, target, source);
return search2 > 0;
}
}
public int breadthFirstSearch(final int MAX, Set<String> blockedSet, int[] source, int[] target) {
int blockedSize = blockedSet.size();
int blockedArea = blockedSize * (blockedSize - 1) / 2;
Set<String> visitedSet = new HashSet<String>();
visitedSet.add(Arrays.toString(source));
int visitedCount = 1;
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(source);
while (!queue.isEmpty()) {
int[] cell = queue.poll();
if (cell[0] == target[0] && cell[1] == target[1])
return 2;
for (int[] direction : directions) {
int[] nextCell = {cell[0] + direction[0], cell[1] + direction[1]};
String nextCellStr = Arrays.toString(nextCell);
if (nextCell[0] >= 0 && nextCell[0] < MAX && nextCell[1] >= 0 && nextCell[1] < MAX && !blockedSet.contains(nextCellStr)) {
if (visitedSet.add(nextCellStr)) {
queue.offer(nextCell);
visitedCount++;
if (visitedCount > blockedArea)
return 1;
}
}
}
}
return 0;
}
}