problem1036

README

< Previous 　　　　　　　　　　　　　　　　 Next >

1036. Escape a Large Maze (Hard)

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

Related Topics

[Breadth-first Search]

Hints

Hint 1

If we become stuck, there's either a loop around the source or around the target.

Hint 2

If there is a loop around say, the source, what is the maximum number of squares it can have?

Documentation

Index

• Constants

Constants

const M = 1e6

M is length and width of the large maze

const MAX = 19900

MAX is the largest number of points that can be enclosed by blocked because of len(blocked)<=200