跳转至

3882. 网格图中最小异或路径

来源第 179 场双周赛 Q3难度中等分数1770

题目描述

给你一个大小为 m * n 的二维整数数组 grid。

你从 左上角 的单元格 (0, 0) 出发,想要到达 右下角 的单元格 (m - 1, n - 1)。

在每一步中,你 可以 向右或向下 移动。

路径的 代价 定义为该路径上所有单元格(包括 起点和终点)的值的 按位异或。

返回从 (0, 0) 到 (m - 1, n - 1) 的所有有效路径中 最小 的可能异或值。

 

示例 1:

输入: grid = [[1,2],[3,4]]

输出: 6

解释:

有两条有效路径:

  • (0, 0) → (0, 1) → (1, 1),异或值为:1 XOR 2 XOR 4 = 7
  • (0, 0) → (1, 0) → (1, 1),异或值为:1 XOR 3 XOR 4 = 6

所有有效路径中的最小异或值为 6。

示例 2:

输入: grid = [[6,7],[5,8]]

输出: 9

解释:

有两条有效路径:

  • (0, 0) → (0, 1) → (1, 1),异或值为:6 XOR 7 XOR 8 = 9
  • (0, 0) → (1, 0) → (1, 1),异或值为:6 XOR 5 XOR 8 = 11

所有有效路径中的最小异或值为 9。

示例 3:

输入: grid = [[2,7,5]]

输出: 0

解释:

只有一条有效路径:

  • (0, 0) → (0, 1) → (0, 2),异或值为:2 XOR 7 XOR 5 = 0

这条路径的异或值为 0,这是可能达到的最小值。

 

提示:

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

解法

方法一:动态规划

思考

只能向右或向下走,求整条路径异或的最小值。格子数 \(mn \le 1000\),格值小于 \(2^{10}\),路径条数仍随行列组合指数增长,逐条枚举不可行。

异或不具备比较意义下的最优子结构。前缀异或更小,再接上后面的格子,总异或仍可能更大,每一种已经出现的异或都要保留。

到达某一格之后,后续选择只取决于当前异或。状态取 \((i,j,k)\),表示走到 \((i,j)\) 且路径异或为 \(k\) 是否可达。 \(k < 1024\),状态量约 \(10^6\)。

转移只有右、下两个方向,按行优先扫描时上方和左方已经算完。用布尔数组 \(f[i][j][k]\) 记录可达性,当前格值为 \(x\) 时从异或 \(k \oplus x\) 接过来;右下角从小到大第一个为真的 \(k\) 就是答案。

定义 \(f[i][j][k]\) 表示能否从 \((0,0)\) 走到 \((i,j)\),且路径上全部格子值的按位异或等于 \(k\)。

设网格最大值为 \(M\)。路径异或落在 \([0,mx)\) 内,其中 \(mx=2^{b}\), \(b\) 为 \(M\) 的二进制位数; \(M=0\) 时 \(b=0\), \(mx=1\)。格值不超过 \(1023\),故 \(mx\le 1024\)。

起点的路径只含自身,因此 \(f[0][0][\textit{grid}[0][0]]=\textit{true}\)。

按先行后列的顺序处理格子 \((i,j)\),记其值为 \(x\)。若它不是起点,则枚举 \(k\in[0,mx)\)。由 \((k\oplus x)\oplus x=k\) 可知,进入该格前的异或是 \(k\oplus x\):

  • 当 \(i>0\) 且 \(f[i-1][j][k\oplus x]\) 为真时,可以从上方进入,令 \(f[i][j][k]=\textit{true}\);
  • 当 \(j>0\) 且 \(f[i][j-1][k\oplus x]\) 为真时,可以从左方进入,令 \(f[i][j][k]=\textit{true}\)。

只允许向右或向下,扫描到 \((i,j)\) 时上方与左方都已完成。最后取 \(f[m-1][n-1]\) 中最小的为真的 \(k\)。从左上角到右下角至少有一条路径,这个 \(k\) 一定存在。

时间复杂度 \(O(mn mx)\),空间复杂度 \(O(mn mx)\)。其中 \(m\)、 \(n\) 为网格的行数与列数, \(mx\le 1024\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mx = 1 << (max(max(row) for row in grid)).bit_length()
        f = [[[False] * mx for _ in range(n)] for _ in range(m)]
        f[0][0][grid[0][0]] = True
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if i > 0 or j > 0:
                    for k in range(mx):
                        if i > 0 and f[i - 1][j][k ^ x]:
                            f[i][j][k] = True
                        if j > 0 and f[i][j - 1][k ^ x]:
                            f[i][j][k] = True
        return next(k for k in range(mx) if f[m - 1][n - 1][k])
 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
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }
        mx = 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(mx));
        boolean[][][] f = new boolean[m][n][mx];
        f[0][0][grid[0][0]] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        if (i > 0 && f[i - 1][j][k ^ x]) {
                            f[i][j][k] = true;
                        }
                        if (j > 0 && f[i][j - 1][k ^ x]) {
                            f[i][j][k] = true;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[m - 1][n - 1][k]) {
                return k;
            }
        }
    }
}
 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
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int mx = 0;
        for (auto& row : grid) {
            for (int x : row) {
                mx = max(mx, x);
            }
        }
        mx = 1 << bit_width(static_cast<unsigned>(mx));
        vector<vector<vector<char>>> f(m, vector<vector<char>>(n, vector<char>(mx, 0)));
        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        if (i > 0 && f[i - 1][j][k ^ x]) {
                            f[i][j][k] = 1;
                        }
                        if (j > 0 && f[i][j - 1][k ^ x]) {
                            f[i][j][k] = 1;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[m - 1][n - 1][k]) {
                return k;
            }
        }
    }
};
 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
func minCost(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    mx := 0
    for _, row := range grid {
        for _, x := range row {
            if x > mx {
                mx = x
            }
        }
    }
    mx = 1 << bits.Len(uint(mx))
    f := make([][][]bool, m)
    for i := range f {
        f[i] = make([][]bool, n)
        for j := range f[i] {
            f[i][j] = make([]bool, mx)
        }
    }
    f[0][0][grid[0][0]] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            x := grid[i][j]
            if i > 0 || j > 0 {
                for k := 0; k < mx; k++ {
                    if i > 0 && f[i-1][j][k^x] {
                        f[i][j][k] = true
                    }
                    if j > 0 && f[i][j-1][k^x] {
                        f[i][j][k] = true
                    }
                }
            }
        }
    }
    for k := 0; ; k++ {
        if f[m-1][n-1][k] {
            return k
        }
    }
}
 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
function minCost(grid: number[][]): number {
    const m = grid.length,
        n = grid[0].length;
    let mx = 0;
    for (const row of grid) {
        for (const x of row) {
            mx = Math.max(mx, x);
        }
    }
    mx = 1 << (32 - Math.clz32(mx));
    const f: boolean[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => new Array<boolean>(mx).fill(false)),
    );
    f[0][0][grid[0][0]] = true;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const x = grid[i][j];
            if (i > 0 || j > 0) {
                for (let k = 0; k < mx; k++) {
                    if (i > 0 && f[i - 1][j][k ^ x]) {
                        f[i][j][k] = true;
                    }
                    if (j > 0 && f[i][j - 1][k ^ x]) {
                        f[i][j][k] = true;
                    }
                }
            }
        }
    }
    for (let k = 0; ; k++) {
        if (f[m - 1][n - 1][k]) {
            return k;
        }
    }
}

方法二:动态规划(滚动数组)

思考

方法一为每个格子保留全部异或可达性,空间随 \(mn\) 增长。格子 \((i,j)\) 只读取正上方和正左方,行优先扫描时这两处已经结束。上一行在进入当前行时仍然完整,当前行只需要已经写下的左邻,因此两行滚动数组就够。转移仍按格值 \(x\) 回看 \(k \oplus x\),答案还是右下角最小的可达异或,空间降到 \(O(n mx)\)。

定义 \(f[i \bmod 2][j][k]\) 表示能否从 \((0,0)\) 走到第 \(i\) 行第 \(j\) 列,且路径上全部格子值的按位异或等于 \(k\)。 \(mx\) 的取法与方法一相同,起点同样有 \(f[0][0][\textit{grid}[0][0]]=\textit{true}\)。

按先行后列的顺序处理格子 \((i,j)\),记其值为 \(x\)。若它不是起点,则枚举 \(k\in[0,mx)\)。行下标对 \(2\) 取模后,当前槽位可能留有更早一行的结果,因此先把 \(f[i \bmod 2][j][k]\) 置为假,再检查上方和左方:

  • 当 \(i>0\) 且 \(f[(i-1)\bmod 2][j][k\oplus x]\) 为真时,可以从上方进入,令 \(f[i \bmod 2][j][k]=\textit{true}\);
  • 当 \(j>0\) 且 \(f[i \bmod 2][j-1][k\oplus x]\) 为真时,可以从左方进入,令 \(f[i \bmod 2][j][k]=\textit{true}\)。

第 \(i\) 行写在下标 \(i \bmod 2\),上一行留在 \((i-1)\bmod 2\),左方与当前格共用这一行。最后取 \(f[(m-1)\bmod 2][n-1]\) 中最小的为真的 \(k\)。从左上角到右下角至少有一条路径,这个 \(k\) 一定存在。

时间复杂度 \(O(mn mx)\),空间复杂度 \(O(n mx)\)。其中 \(m\)、 \(n\) 为网格的行数与列数, \(mx\le 1024\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mx = 1 << (max(max(row) for row in grid)).bit_length()
        f = [[[False] * mx for _ in range(n)] for _ in range(2)]
        f[0][0][grid[0][0]] = True
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if i > 0 or j > 0:
                    for k in range(mx):
                        f[i & 1][j][k] = False
                        if i > 0 and f[(i - 1) & 1][j][k ^ x]:
                            f[i & 1][j][k] = True
                        if j > 0 and f[i & 1][j - 1][k ^ x]:
                            f[i & 1][j][k] = True
        return next(k for k in range(mx) if f[(m - 1) & 1][n - 1][k])
 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
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }
        mx = 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(mx));
        boolean[][][] f = new boolean[2][n][mx];
        f[0][0][grid[0][0]] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        f[i & 1][j][k] = false;
                        if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                            f[i & 1][j][k] = true;
                        }
                        if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                            f[i & 1][j][k] = true;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[(m - 1) & 1][n - 1][k]) {
                return k;
            }
        }
    }
}
 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
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int mx = 0;
        for (auto& row : grid) {
            for (int x : row) {
                mx = max(mx, x);
            }
        }
        mx = 1 << bit_width(static_cast<unsigned>(mx));
        vector<vector<vector<char>>> f(2, vector<vector<char>>(n, vector<char>(mx, 0)));
        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        f[i & 1][j][k] = 0;
                        if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                            f[i & 1][j][k] = 1;
                        }
                        if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                            f[i & 1][j][k] = 1;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[(m - 1) & 1][n - 1][k]) {
                return k;
            }
        }
    }
};
 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
func minCost(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    mx := 0
    for _, row := range grid {
        for _, x := range row {
            if x > mx {
                mx = x
            }
        }
    }
    mx = 1 << bits.Len(uint(mx))
    f := make([][][]bool, 2)
    for i := range f {
        f[i] = make([][]bool, n)
        for j := range f[i] {
            f[i][j] = make([]bool, mx)
        }
    }
    f[0][0][grid[0][0]] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            x := grid[i][j]
            if i > 0 || j > 0 {
                for k := 0; k < mx; k++ {
                    f[i&1][j][k] = false
                    if i > 0 && f[(i-1)&1][j][k^x] {
                        f[i&1][j][k] = true
                    }
                    if j > 0 && f[i&1][j-1][k^x] {
                        f[i&1][j][k] = true
                    }
                }
            }
        }
    }
    for k := 0; ; k++ {
        if f[(m-1)&1][n-1][k] {
            return k
        }
    }
}
 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
function minCost(grid: number[][]): number {
    const m = grid.length,
        n = grid[0].length;
    let mx = 0;
    for (const row of grid) {
        for (const x of row) {
            mx = Math.max(mx, x);
        }
    }
    mx = 1 << (32 - Math.clz32(mx));
    const f: boolean[][][] = Array.from({ length: 2 }, () =>
        Array.from({ length: n }, () => new Array<boolean>(mx).fill(false)),
    );
    f[0][0][grid[0][0]] = true;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const x = grid[i][j];
            if (i > 0 || j > 0) {
                for (let k = 0; k < mx; k++) {
                    f[i & 1][j][k] = false;
                    if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                        f[i & 1][j][k] = true;
                    }
                    if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                        f[i & 1][j][k] = true;
                    }
                }
            }
        }
    }
    for (let k = 0; ; k++) {
        if (f[(m - 1) & 1][n - 1][k]) {
            return k;
        }
    }
}

评论