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:

1. 0 <= blocked.length <= 200
2. blocked[i].length == 2
3. 0 <= blocked[i][j] < 10^6
4. source.length == target.length == 2
5. 0 <= source[i][j], target[i][j] < 10^6
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;
    }
}

All Problems

All Solutions