来源第 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;
}
}
}
|