Skip to content

1368. Minimum Cost to Make at Least One Valid Path in a Grid 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
class Solution {
 public:
  int minCost(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<int>> mem(m, vector<int>(n, -1));
    queue<pair<int, int>> q;

    dfs(grid, 0, 0, /*cost=*/0, q, mem);

    for (int cost = 1; !q.empty(); ++cost)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs)
          dfs(grid, i + dx, j + dy, cost, q, mem);
      }

    return mem.back().back();
  }

 private:
  const vector<pair<int, int>> dirs{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  void dfs(const vector<vector<int>>& grid, int i, int j, int cost,
           queue<pair<int, int>>& q, vector<vector<int>>& mem) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return;
    if (mem[i][j] != -1)
      return;

    mem[i][j] = cost;
    q.emplace(i, j);
    const auto [dx, dy] = dirs[grid[i][j] - 1];
    dfs(grid, i + dx, j + dy, cost, q, mem);
  }
};

 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
class Solution {
  public int minCost(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][] mem = new int[m][n];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();

    dfs(grid, 0, 0, /*cost=*/0, q, mem);

    for (int cost = 1; !q.isEmpty(); ++cost)
      for (int sz = q.size(); sz > 0; --sz) {
        Pair<Integer, Integer> pair = q.poll();
        final int i = pair.getKey();
        final int j = pair.getValue();
        for (int[] dir : dirs)
          dfs(grid, i + dir[0], j + dir[1], cost, q, mem);
      }

    return mem[m - 1][n - 1];
  }

  private static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  private void dfs(int[][] grid, int i, int j, int cost, Queue<Pair<Integer, Integer>> q,
                   int[][] mem) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return;
    if (mem[i][j] != -1)
      return;

    mem[i][j] = cost;
    q.add(new Pair<>(i, j));
    int[] dir = dirs[grid[i][j] - 1];
    dfs(grid, i + dir[0], j + dir[1], cost, q, mem);
  }
}

 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
class Solution:
  def minCost(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    dp = [[-1] * n for _ in range(m)]
    q = collections.deque()

    def dfs(i: int, j: int, cost: int) -> None:
      if i < 0 or i == m or j < 0 or j == n:
        return
      if dp[i][j] != -1:
        return

      dp[i][j] = cost
      q.append((i, j))
      dx, dy = dirs[grid[i][j] - 1]
      dfs(i + dx, j + dy, cost)

    dfs(0, 0, 0)

    cost = 0
    while q:
      cost += 1
      for _ in range(len(q)):
        i, j = q.popleft()
        for dx, dy in dirs:
          dfs(i + dx, j + dy, cost)

    return dp[-1][-1]