Escape a Large Maze LeetCode solution in Java

1
class Solution {
2
  static final int limit = 1000000; // boundary check
3

4
  public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
5
    Set<String> blocks = new HashSet<>(); // HashSet to reduce the access time from O(N)-> O(1)
6

7
    for (int block[] : blocked)
8
      blocks.add(
9
          block[0] + "-"
10
              + block[1]); // putting the blocked node into the HashSet to access it at O(1)
11

12
    return bfsRange(source, target, blocks) && bfsRange(target, source, blocks); // sector division
13

14
    /*checking for both the case that the source is blocked or the target is blocked
15
     *if one of them is blocked we return false
16
     *since it is not practical to traverse each node, it will provide us with TLE
17
     */
18
  }
19

20
  /* Formula ::
21
   * shortest arc(displacement) of 1/4 sector of circel is a* 2^1/2
22
   * Area of the triangular sector is 1/2 * ( r{base} * r{height} )
23
   * Number of minimum shell to cover to move ahed of sector or boundary if possible = 0 + 1 + 2 + 3 + ... + 199 = 19900 (A.P)
24
   */
25

26
  public boolean bfsRange(
27
      int[] source,
28
      int[] target,
29
      Set<String>
30
          blocks) { // we simply do bsf to check the circular quadrant 1/4th boundary of the sector
31

32
    Set<String> visited =
33
        new HashSet<>(); // visited hash set is so that we dont visit the visited cell again and the
34
    // access time is O(1)
35
    Queue<int[]> q = new LinkedList<>(); // as we use in BT
36

37
    q.offer(source); // adding the starting BFS node to the Queue
38

39
    visited.add(
40
        source[0] + "-" + source[1]); // marking it as visited so that we dont traverse it again
41

42
    int count = 0; // number of node traverse total outside + inside
43
    while (!q.isEmpty()) { // r m* w a*
44
      int temp[] = q.poll(); // poling the node
45
      count += 1; // counting the number of node traverse
46

47
      int trav[][] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}}; // Traversing in 4-Direction
48

49
      for (int direction[] : trav) {
50
        int i = temp[0] + direction[0];
51
        int j = temp[1] + direction[1];
52

53
        String key = (i + "-" + j);
54

55
        if (i < 0
56
            || j < 0
57
            || i >= limit
58
            || j >= limit
59
            || visited.contains(key)
60
            || blocks.contains(key))
61
          continue; // base case 1)checking the index 2)We dont visit the blocked node 3) we dont
62
        // visit the visited node
63

64
        if (i == target[0]
65
            && j
66
                == target[
67
                    1]) // when we find the target within the boundary(same sector or the quadrand)
68
          // we just return true //best case saves a lot of time
69
          return true;
70

71
        visited.add(key); // marking the node as visited and adding it to the Queue
72

73
        q.offer(new int[] {i, j}); // Expaning the search for path and adding the node
74

75
        if (count > 19900) // number of cell, crossing the boundary limit
76
        return true; // path exists from this node
77
      }
78
    }
79
    return false; // no path, to reach the node//boundary blocked us
80
  }
81
} // Please do Upvote, it helps a lot