The line that decides this problem sits in the constraints: `0 <= grid[i][j] <= 1023`. XOR never carries, so no path cost can grow past ten bits, and every value a path can produce lives in `[0, 1024)`. That replaces the question "what is the cheapest cost here" with "which costs are reachable here", and 1024 candidates per cell fit in one `bitset`. My first instinct was the usual grid-DP reflex: keep the minimum XOR reachable at each cell and take the better of the two predecessors. It is wrong, and the way it breaks is the useful part. XOR has no monotonicity under composition, so a smaller prefix does not stay smaller once you fold the rest of the path into it. On `[[0,2,0],[3,0,1]]` the prefixes arriving at cell `(1,1)` are 2 and 3, the per-cell minimum keeps 2, the last cell contributes 1, and the greedy answer comes out 3 while the real answer is 2 — reached through the prefix it threw away. So the state has to be a set, not a number. `dp[i][j]` is the set of XOR values some path from `(0, 0)` to `(i, j)` can produce; the transition unions the two incoming sets and XORs every member with `grid[i][j]`. The answer is the lowest set bit of `dp[m-1][n-1]`. ## Worked example Same grid as above, `[[0,2,0],[3,0,1]]`, written as the bit sets per cell: - `(0,0)`: `{0}` — the start cell contributes `grid[0][0] = 0`. - `(0,1)`: `{0 ^ 2}` = `{2}`. `(0,2)`: `{2 ^ 0}` = `{2}`. - `(1,0)`: `{0 ^ 3}` = `{3}`. - `(1,1)`: incoming `{2}` from above and `{3}` from the left, XOR with 0, so `{2, 3}`. This is the cell where the greedy loses 3. - `(1,2)`: incoming `{2}` from above and `{2, 3}` from the left, XOR with 1, so `{3, 2}`. Lowest bit set in the corner is 2, which matches the path `(0,0) -> (1,0) -> (1,1) -> (1,2)` with `0 ^ 3 ^ 0 ^ 1 = 2`. ## Complexity - Time O(m·n·V) with V = 1024 — every cell scans the whole value universe once, which the `m * n <= 1000` bound caps near a million bit tests. - Space O(m·n·V) bits — one 1024-bit set per cell, 128 KB at the ceiling. ## Code (C++) ```cpp class Solution { public: int minCost(vector>& grid) { const int K = 1024; // values are <= 1023, so every XOR stays below 1024 int m = grid.size(), n = grid[0].size(); vector>> dp(m, vector>(n)); dp[0][0].set(grid[0][0]); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) continue; bitset in; if (i > 0) in |= dp[i - 1][j]; if (j > 0) in |= dp[i][j - 1]; int v = grid[i][j]; for (int x = 0; x < K; ++x) if (in.test(x)) dp[i][j].set(x ^ v); } } for (int x = 0; x < K; ++x) if (dp[m - 1][n - 1].test(x)) return x; return -1; // unreachable: the single-cell grid already sets a bit } }; ``` ## One note I scanned the incoming set with a plain `for (int x = 0; x < K; ++x)` and `in.test(x)` rather than the GNU `_Find_first()` / `_Find_next()` pair. Those would skip the empty slots, but the constraint caps the total work near a million tests anyway, and I would rather not lean on a non-standard member of `bitset` for a constant factor that does not matter here. The same reasoning is why `const int K = 1024;` is declared const: it has to be a constant expression to serve as the `bitset` template argument, and a plain `int` would not compile. The `return -1` at the bottom is unreachable — even a one-cell grid sets a bit — and stays as a guard the compiler is happy with. The takeaway I want to keep: before reaching for a greedy, check whether the cost function is monotone under the operation that composes paths. XOR is not, so any DP that compresses a cell down to one best value is unsound. When that happens, read the value range next: a universe of 10 bits is small enough to make the state the full set of reachable costs, which is exact where the compression was not. Flip the final scan around and the same table answers "maximum XOR" or "is cost v reachable" without touching the DP.