3882. Minimum XOR Path in a Grid

2026, Oct 27 2 mins read

1. Description

Given an m x n integer matrix grid, travel from (0,0) to (m - 1,n - 1), moving only one cell right or down at each step.
A path’s cost is the bitwise XOR of every cell value it visits, including both endpoints.
Return the smallest cost achievable by any such path.

2. Example

Example 1

Input: grid = [[1,2],[3,4]]
Output: 6
Explanation: Moving right then down gives 1 XOR 2 XOR 4 = 7. Moving down then right gives 1 XOR 3 XOR 4 = 6, which is smaller.

Example 2

Input: grid = [[6,7],[5,8]]
Output: 9
Explanation: The two paths have costs 6 XOR 7 XOR 8 = 9 and 6 XOR 5 XOR 8 = 11. The minimum is 9.

Example 3

Input: grid = [[2,7,5]]
Output: 0
Explanation: The single row permits just one path, whose cost is 2 XOR 7 XOR 5 = 0.

3. Constraints

1 <= m == grid.length <= 1000
1 <= n == grid[i].length <= 1000
m * n <= 1000
0 <= grid[i][j] <= 1023

4. Solutions

Dynamic Programming

m = grid.size(), n = grid.front().size(), U = 1024
Time complexity: O(mnU)
Space complexity: O(nU)

 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
class Solution {
public:
    int minCost(vector<vector<int>> &grid) {
        const int m = grid.size(), n = grid.front().size();

        vector<bitset<1024>> values(n);
        values[0][0] = 1;

        for (int i = 0; i < m; ++i) {
            bitset<1024> value;
            for (int k = 0; k < 1024; ++k) {
                if (values[0][k]) {
                    value[k ^ grid[i][0]] = 1;
                }
            }
            values[0] = value;

            for (int j = 1; j < n; ++j) {
                bitset<1024> value;
                for (int k = 0; k < 1024; ++k) {
                    if (values[j - 1][k] || values[j][k]) {
                        value[k ^ grid[i][j]] = 1;
                    }
                }

                values[j] = value;
            }
        }

        for (int k = 0; k < 1024; ++k) {
            if (values.back()[k]) {
                return k;
            }
        }

        return -1;
    }
};

Search

Tags