1.4.3 Grid 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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

/*

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. Processing rows from top
to bottom and columns from left to right makes predecessors above and to the left available when a
state is computed.

- `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. The state
  $dp(r, c)$ counts paths to cell $(r, c)$ from the counts above and left. Only the current row is
  retained.
- `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. The state $dp(r, c)$ stores the cheapest cost to cell $(r, c)$. Only the current row of
  costs is retained, while predecessor directions reconstruct one optimal path. If the grid is
  empty, `min_cost` is $0$ and `path` is empty.
- `largest_nonzero_square(a)` returns a tuple (`side`, `top`, `left`) describing a largest
  all-nonzero square in `a`. The state $dp(c)$ is the largest square ending at the current cell in
  column $c$; a nonzero cell extends the minimum of the states above, left, and diagonally
  above-left. If no such square exists, the function returns $(0, -1, -1)$. Overflow warning: Path
  counts and path costs must fit in `int64_t`. Time Complexity:
- O(R*C) per call, 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)`.
- O(C) auxiliary for `largest_nonzero_square(a)`.

*/

#include <algorithm>
#include <cstdint>
#include <tuple>
#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 = blocked.empty() ? 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 = cost.empty() ? 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>> pred(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.
        pred[r][c] = 'U';
      } else {
        dp[c] = dp[c - 1] + cost[r][c];
        pred[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 (pred[r][c] == 'U') {
      r--;
    } else {
      c--;
    }
  }
  std::reverse(path.begin(), path.end());
  return {dp.back(), path};
}

std::tuple<int, int, int> largest_nonzero_square(const std::vector<std::vector<char>> &a) {
  int rows = static_cast<int>(a.size());
  int cols = a.empty() ? 0 : static_cast<int>(a[0].size());
  std::vector<int> dp(cols);
  int best = 0, top = -1, left = -1;
  for (int r = 0; r < rows; r++) {
    int diagonal = 0;
    for (int c = 0; c < cols; c++) {
      int above = dp[c];
      dp[c] = a[r][c] ? 1 + std::min({above, c == 0 ? 0 : dp[c - 1], diagonal}) : 0;
      diagonal = above;
      if (dp[c] > best) {
        best = dp[c];
        top = r - best + 1;
        left = c - best + 1;
      }
    }
  }
  return {best, top, left};
}

/*** 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 && (path == vector<pair<int, int>>{{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}}));

  vector<vector<char>> binary{
      {1, 0, 1, 0, 0},
      {1, 0, 1, 1, 1},
      {1, 1, 1, 1, 1},
      {1, 0, 1, 1, 1},
  };
  assert((largest_nonzero_square(binary) == tuple{3, 1, 2}));
  assert((largest_nonzero_square({{0, 0}}) == tuple{0, -1, -1}));
  return 0;
}