Skip to content

1810. Minimum Path Cost in a Hidden Grid

  • Time: $O(m^2\log m^2)$
  • Space: $O(m^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *  public:
 *   bool canMove(char direction);
 *   int std::move(char direction);
 *   boolean isTarget();
 * };
 */

class Solution {
 public:
  int findShortestPath(GridMaster& master) {
    constexpr int m = 100;
    constexpr int startX = m;
    constexpr int startY = m;
    vector<int> target{m * 2, m * 2};
    vector<vector<int>> grid(m * 2, vector<int>(m * 2, -1));
    vector<vector<bool>> seen(m * 2, vector<bool>(m * 2));

    // Build the grid information by DFS.
    dfs(master, grid, startX, startY, target);

    priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;
    minHeap.push({0, startX, startY});

    // Find the steps by BFS.
    while (!minHeap.empty()) {
      const vector<int> tuple = minHeap.top();
      const int cost = tuple[0];
      const int i = tuple[1];
      const int j = tuple[2];
      minHeap.pop();
      if (i == target[0] && j == target[1])
        return cost;
      if (seen[i][j])
        continue;
      seen[i][j] = true;
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == 2 * m || y < 0 || y == 2 * m)
          continue;
        if (seen[x][y] || grid[x][y] == -1)
          continue;
        const int nextCost = cost + grid[x][y];
        minHeap.push({nextCost, x, y});
      }
    }

    return -1;
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  static constexpr char charTable[4] = {'R', 'D', 'L', 'U'};

  void dfs(GridMaster& master, vector<vector<int>>& grid, int i, int j,
           vector<int>& target) {
    if (master.isTarget()) {
      target[0] = i;
      target[1] = j;
    }

    for (int k = 0; k < 4; ++k) {
      const int x = i + dirs[k][0];
      const int y = j + dirs[k][1];
      const char d = charTable[k];
      const char undoD = charTable[(k + 2) % 4];
      if (master.canMove(d) && grid[x][y] == -1) {
        grid[x][y] = master.move(d);
        dfs(master, grid, x, y, target);
        master.move(undoD);
      }
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *   boolean canMove(char direction);
 *   int move(char direction);
 *   boolean isTarget();
 * }
 */

class Solution {
  public int findShortestPath(GridMaster master) {
    final int m = 100;
    final int startX = m;
    final int startY = m;
    int[] target = {m * 2, m * 2};
    int[][] grid = new int[m * 2][m * 2];
    boolean[][] seen = new boolean[m * 2][m * 2];
    Arrays.stream(grid).forEach(A -> Arrays.fill(A, -1));

    // Build the grid information by DFS.
    dfs(master, grid, startX, startY, target);

    Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2])) {
      { offer(new int[] {startX, startY, 0}); }
    };

    // Find the steps by BFS.
    while (!minHeap.isEmpty()) {
      final int i = minHeap.peek()[0];
      final int j = minHeap.peek()[1];
      final int cost = minHeap.poll()[2];
      if (i == target[0] && j == target[1])
        return cost;
      if (seen[i][j])
        continue;
      seen[i][j] = true;
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == 2 * m || y < 0 || y == 2 * m)
          continue;
        if (seen[x][y] || grid[x][y] == -1)
          continue;
        final int nextCost = cost + grid[x][y];
        minHeap.offer(new int[] {x, y, nextCost});
      }
    }

    return -1;
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  private static final char[] charTable = {'R', 'D', 'L', 'U'};

  private void dfs(GridMaster master, int[][] grid, int i, int j, int[] target) {
    if (master.isTarget()) {
      target[0] = i;
      target[1] = j;
    }

    for (int k = 0; k < 4; ++k) {
      final int x = i + dirs[k][0];
      final int y = j + dirs[k][1];
      final char d = charTable[k];
      final char undoD = charTable[(k + 2) % 4];
      if (master.canMove(d) && grid[x][y] == -1) {
        grid[x][y] = master.move(d);
        dfs(master, grid, x, y, target);
        master.move(undoD);
      }
    }
  }
}