1.3.3 Grid Path DP

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/*

Solves basic dynamic programming problems on a rectangular grid. In grid DP, each cell represents a
state and transitions usually come from already-computed neighboring cells, most commonly the cell
above and the cell to the left. Processing rows from top to bottom and columns from left to right
therefore makes every predecessor available when a state is computed.

For path-counting, `dp[r][c]` stores the number of ways to reach cell $(r, c)$. For minimum-cost
paths, `dp[r][c]` stores the cheapest cost to reach that cell, and a predecessor direction
reconstructs one optimal path. The implementation retains only the current row of path costs while
storing all predecessor directions. The helpers below assume movement only down or right.

- `count_grid_paths(blocked)` returns the number of paths from the upper-left cell to the
  lower-right cell, moving only down or right and avoiding blocked cells marked nonzero.
- `min_cost_grid_path(cost)` returns a pair (`min_cost`, `path`) containing the minimum cost of a
  down/right path from the upper-left cell to the lower-right cell and the cells of one optimal path
  in order. If the grid is empty, `min_cost` is $0$ and `path` is empty.

Overflow warning: Path counts and path costs must fit in `int64_t`.

Time Complexity:
- O(R*C) per call to `count_grid_paths(blocked)` and `min_cost_grid_path(cost)`, where $R$ and $C$
  are the grid dimensions.

Space Complexity:
- O(C) auxiliary for `count_grid_paths(blocked)`.
- O(R*C) auxiliary for predecessor directions, O(C) for path costs, and O(R + C) for the returned
  path from `min_cost_grid_path(cost)`.

*/

#include <algorithm>
#include <cstdint>
#include <utility>
#include <vector>

int64_t count_grid_paths(const std::vector<std::vector<char>> &blocked) {
  int rows = static_cast<int>(blocked.size());
  int cols = rows == 0 ? 0 : static_cast<int>(blocked[0].size());
  if (rows == 0 || cols == 0 || blocked[0][0] || blocked[rows - 1][cols - 1]) {
    return 0;
  }
  std::vector<int64_t> dp(cols);
  dp[0] = 1;
  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (blocked[r][c]) {
        dp[c] = 0;
      } else if (c > 0) {
        dp[c] += dp[c - 1];  // Overflow warning.
      }
    }
  }
  return dp[cols - 1];
}

std::pair<int64_t, std::vector<std::pair<int, int>>> min_cost_grid_path(
    const std::vector<std::vector<int>> &cost
) {
  int rows = static_cast<int>(cost.size());
  int cols = rows == 0 ? 0 : static_cast<int>(cost[0].size());
  if (rows == 0 || cols == 0) {
    return {0, {}};
  }
  std::vector<int64_t> dp(cols);
  std::vector<std::vector<char>> parent(rows, std::vector<char>(cols));
  dp[0] = cost[0][0];
  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (r == 0 && c == 0) {
        continue;
      }
      if (r > 0 && (c == 0 || dp[c] <= dp[c - 1])) {
        dp[c] += cost[r][c];  // Overflow warning.
        parent[r][c] = 'U';
      } else {
        dp[c] = dp[c - 1] + cost[r][c];
        parent[r][c] = 'L';
      }
    }
  }
  // Optional: reconstruct one optimal path.
  std::vector<std::pair<int, int>> path;
  for (int r = rows - 1, c = cols - 1;;) {
    path.emplace_back(r, c);
    if (r == 0 && c == 0) {
      break;
    }
    if (parent[r][c] == 'U') {
      r--;
    } else {
      c--;
    }
  }
  std::reverse(path.begin(), path.end());
  return {dp.back(), path};
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<vector<char>> blocked{
      {0, 0, 0},
      {0, 1, 0},
      {0, 0, 0},
  };
  assert(count_grid_paths(blocked) == 2);

  vector<vector<int>> cost{
      {1, 3, 1},
      {1, 5, 1},
      {4, 2, 1},
  };
  auto [min_cost, path] = min_cost_grid_path(cost);
  assert(min_cost == 7);
  assert((path == vector<pair<int, int>>{{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}}));
  return 0;
}