Leetcode solution 1036: Escape a Large Maze

包子面试培训

发布于 2019-06-17 11:31:24

8300

发布于 2019-06-17 11:31:24

文章被收录于专栏：包子铺里聊IT

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:

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

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     }