New leetcode solution video on YouTube.com/baozitraining
Leetcode solution 1036: Escape a Large Maze
Blogger: https://blog.baozitraining.org/2019/05/leetcode-solution-1036-escape-large-maze.html
Youtube: https://youtu.be/bVqxkkZ0a1M
博客园: https://www.cnblogs.com/baozitraining/p/10945962.html
B 站:
https://www.bilibili.com/video/av53975943
Problem Statement
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:
代码语言：javascript复制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:
代码语言：javascript复制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 <= 200blocked[i].length == 20 <= blocked[i][j] < 10^6source.length == target.length == 20 <= source[i][j], target[i][j] < 10^6source != target
Hints
- If we become stuck, there's either a loop around the source or around the target.
- If there is a loop around say, the source, what is the maximum number of squares it can have?
Problem link
Video Tutorial
You can find the detailed Youtube video tutorial here
国内：B站的视频戳这里
Thought Process
At first, I am puzzled why this problem would be a hard one. It seems simply applying a BFS would get the answer. So here we go.
Brute force, simple BFS
Of course it will hit memory limit because I am allocating a 2-dimensional visited array. Assume boolean is 8 bit -> 1B, 1 Million * 1 Million = 1TB, OMG, immediately using a set instead.
P.S. fun fact, you can use this method to test how much memory leetcode allocate to this problem, you can use binary search and memory is around 300MB
However, this would start hitting Time Limit Exception. Now I begin to notice a few constrains, e.g., the block size is only 200 while the grid is 1M*1M. Simply going from source to target worst case would cause a timeout.
Next thought would be does it help if we sort the block array? While we are doing the BFS, if the block is already larger/smaller than the max/min of the block, we can early stop. However, this won't help if we simply place a block near the target. Also, this would be a nightmare to implement.
Check block loops on source and target
Following the two hints, it would be natural to come up with this idea. Given such huge contrast between the block size (0,200) and the grid size (1M, 1M), all we need to do is to check if there is any loops built by block on source and target b/c if there is a loop, we cannot explore outside of the loop. However, notice if target and source are in the same loop, then we are fine.
There are two ways to early stop this loop checking. One way is to count the BFS steps, the other way is to follow the hints, given 200 blocks, what's the max area it can cover. Given the length 200, Fig 2 in the below graph can result in the largest area. Therefore, we can early terminate the BFS search once we covered more than 19900 blocks. (We can relax this a bit to 20000, doesn't matter)
- Fig 1 area = 100 * 100 = 10000
- Fig 2 area = 1 2 3 ... 199 = (1 199)*199/2 = 19900
- Fig 3 area = 1 * 200 = 200
- Fig 4 area = 790 (2*Pi*R = 100, thus R = 15.92, Pi * R^2 = 790 )
Solutions
Brute force, simple BFS
1 private final int[] xDirection = {1, 0, -1, 0};
2 private final int[] yDirection = {0, -1, 0, 1};
3 private final int ONE_MILLION = 1000000;
4
5 public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
6 if (blocked == null || source == null || target == null) {
7 return false;
8 }
9 Set<String> blockLookup = this.indexBlockedMatrixToSet(blocked);
10
11 int m = ONE_MILLION;
12 int n = ONE_MILLION;
13
14 Set<String> visited = new HashSet<>();
15
16 Queue<String> queue = new LinkedList<>();
17
18 String sourceString = source[0] "," source[1];
19 queue.offer(sourceString);
20 visited.add(sourceString);
21
22 while (!queue.isEmpty()) {
23 String[] curBlock = queue.poll().split(",");
24 int curX = Integer.parseInt(curBlock[0]);
25 int curY = Integer.parseInt(curBlock[1]);
26
27 if (curX == target[0] && curY == target[1]) {
28 return true;
29 }
30
31 for (int i = 0; i < 4; i ) {
32 int nextX = curX xDirection[i];
33 int nextY = curY yDirection[i];
34 if (this.shouldExplore(nextX, nextY, ONE_MILLION, ONE_MILLION, blockLookup, visited)) {
35 String nextKey = nextX "," nextY;
36 visited.add(nextKey);
37 queue.offer(nextKey);
38 }
39 }
40 }
41
42 return false;
43 }
44
45
46 private boolean shouldExplore(
47 int x,
48 int y,
49 int row,
50 int col,
51 Set<String> blockLookup,
52 Set<String> visited) {
53 if (!(x >= 0 && x < row && y >=0 && y < col)) {
54 return false;
55 }
56
57 String index = x "," y;
58 if (visited.contains(index)) {
59 return false;
60 }
61 if (blockLookup.contains(index)) {
62 return false;
63 }
64
65 return true;
66 }
67
68 private Set<String> indexBlockedMatrixToSet(int[][] blocked) {
69 Set<String> lookup = new HashSet<>();
70
71 for (int i = 0; i < blocked.length; i ) {
72 int x = blocked[i][0];
73 int y = blocked[i][1];
74 String index = x "," y;
75 lookup.add(index);
76 }
77 return lookup;
78 }Time Complexity: O(N), N = 1M * 1M, essentially need to cover the entire huge grid
Space Complexity: O(N), N = 1M*1M, essentially all the nodes need to be put to visited set
Check block loops on source and target
1 private final int[] xDirection = {1, 0, -1, 0};
2 private final int[] yDirection = {0, -1, 0, 1};
3 private final int ONE_MILLION = 1000000;
4 private final int MAX_COUNT_THRESHOLD = 20000;
5
6 public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
7 if (blocked == null || source == null || target == null) {
8 return false;
9 }
10
11 Set<String> blockLookup = this.indexBlockedMatrixToSet(blocked);
12 boolean isSourceLoop = this.isLoopAroundPoint(source, target, blockLookup);
13 if (isSourceLoop) {
14 return false;
15 }
16
17 boolean isTargetLoop = this.isLoopAroundPoint(target, source, blockLookup);
18 if (isTargetLoop) {
19 return false;
20 }
21
22 return true;
23 }
24
25 private boolean isLoopAroundPoint(int[] source, int[] target, Set<String> blockLookup) {
26 int count = 0;
27
28 Set<String> visited = new HashSet<>();
29 Queue<String> queue = new LinkedList<>();
30
31 String index = source[0] "," source[1];
32 queue.offer(index);
33 visited.add(index);
34
35 while (!queue.isEmpty()) {
36 String[] curBlock = queue.poll().split(",");
37 int curX = Integer.parseInt(curBlock[0]);
38 int curY = Integer.parseInt(curBlock[1]);
39
40 // here think about
41 if (count >= MAX_COUNT_THRESHOLD) {
42 return false;
43 }
44
45 if (curX == target[0] && curY == target[1]) {
46 return false;
47 }
48
49 for (int i = 0; i < 4; i ) {
50 int nextX = curX xDirection[i];
51 int nextY = curY yDirection[i];
52
53 if (this.shouldExplore(nextX, nextY, ONE_MILLION, ONE_MILLION, blockLookup, visited)) {
54 String nextKey = nextX "," nextY;
55 count ;
56 visited.add(nextKey);
57 queue.offer(nextKey);
58 }
59 }
60 }
61
62 return true;
63 }
64
65 private boolean shouldExplore(
66 int x,
67 int y,
68 int row,
69 int col,
70 Set<String> blockLookup,
71 Set<String> visited) {
72 if (!(x >= 0 && x < row && y >=0 && y < col)) {
73 return false;
74 }
75
76 String index = x "," y;
77 if (visited.contains(index)) {
78 return false;
79 }
80 if (blockLookup.contains(index)) {
81 return false;
82 }
83
84 return true;
85 }
86
87 private Set<String> indexBlockedMatrixToSet(int[][] blocked) {
88 Set<String> lookup = new HashSet<>();
89
90 for (int i = 0; i < blocked.length; i ) {
91 int x = blocked[i][0];
92 int y = blocked[i][1];
93 String index = x "," y;
94 lookup.add(index);
95 }
96 return lookup;
97 }Time Complexity: O(N), N in terms of block size
Space Complexity: O(N), N in terms of block size
References
- Leetcode discussion using BFS steps
- Leetcode discussion using BFS area
