LeetCode 3459. 最长 V 形对角线段的长度 — Java 实现
题目概述
- 给定 `n × m` 的矩阵 `grid`，元素值为 `0`、`1` 或 `2`。
- V 形对角线段 规则：
- 必须从 `1` 开始。
- 后续元素按 `2, 0, 2, 0, ...` 交替。
- 沿四个对角线方向之一移动。
- 最多允许一次顺时针 90° 转向。
- 返回最长合法路径的长度，不存在则返回 `0`。
---
核心思路：DFS + 记忆化搜索
状态定义：`memo[i][j][dir][turn]` 表示从位置 `(i, j)` 出发，当前移动方向为 `dir`，是否还能转向 `turn`（0/1）时，往后能延伸的最长路径长度。
四个对角方向（按顺时针排列）：
- `0`: 右下 `(1, 1)`
- `1`: 左下 `(1, -1)`
- `2`: 左上 `(-1, -1)`
- `3`: 右上 `(-1, 1)`
顺时针 90° 转向：`dir → (dir + 1) % 4`
目标值计算：
- 当前值为 `1` → 下一步期望 `2`
- 当前值为 `2` → 下一步期望 `0`
- 当前值为 `0` → 下一步期望 `2`
- 统一公式：`next = grid[i][j] == 1 ? 2 : (2 - grid[i][j])`
递归逻辑：
1. 沿当前方向前进一步，检查是否越界且值匹配。
2. 选择一：继续直行。
3. 选择二：若还能转向，则顺时针转 90° 后继续。
4. 取两者最大值 + 1（当前步）。
---
Java 代码
```java
class Solution {
// 四个对角方向：右下、左下、左上、右上（顺时针排列）
private static final int[][] DIRS = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
// 记忆化数组：memo[i][j][dir][turn]
// turn=1 表示还能转向，turn=0 表示已转过
private int[][][][] memo;
private int[][] grid;
private int m, n;
public int lenOfVDiagonal(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
// 初始化记忆化数组，-1 表示未计算
memo = new int[m][n][4][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 4; d++) {
memo[i][j][d][0] = -1;
memo[i][j][d][1] = -1;
}
}
}
int ans = 0;
// 枚举所有起点（值为 1 的位置）
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// 尝试四个初始方向
for (int d = 0; d < 4; d++) {
// +1 包含起点本身
ans = Math.max(ans, dfs(i, j, d, 1) + 1);
}
}
}
}
return ans;
}
/**
* 返回从 (i, j) 出发，沿方向 dir，是否还能转向 turn 时，
* 后续路径的最大长度（不包含当前点）
*/
private int dfs(int i, int j, int dir, int turn) {
// 计算下一步坐标
int ni = i + DIRS[dir][0];
int nj = j + DIRS[dir][1];
// 计算下一步期望值
int target = grid[i][j] == 1 ? 2 : (2 - grid[i][j]);
// 越界或值不匹配，路径终止
if (ni < 0 || ni >= m || nj < 0 || nj >= n || grid[ni][nj] != target) {
return 0;
}
// 检查记忆化
if (memo[ni][nj][dir][turn] != -1) {
return memo[ni][nj][dir][turn];
}
// 选择一：继续直行
int res = dfs(ni, nj, dir, turn);
// 选择二：若还能转向，顺时针转 90° 后继续
if (turn == 1) {
int turnRes = dfs(ni, nj, (dir + 1) % 4, 0);
res = Math.max(res, turnRes);
}
// 记忆化并返回（+1 包含当前步 ni,nj）
memo[ni][nj][dir][turn] = res + 1;
return res + 1;
}
}
```
---
复杂度分析
指标 复杂度 说明
时间 O(n × m × 4 × 2) = O(nm) 每个状态 `(i, j, dir, turn)` 只计算一次
空间 O(n × m × 4 × 2) = O(nm) 记忆化数组
---
验证示例
输入 输出 说明
`[[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]` `5` `(0,2)→(1,3)→(2,4)` 右转后 `(3,3)→(4,2)`
`[[2,2,2,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]` `4` `(2,3)→(3,2)` 右转后 `(2,1)→(1,0)`
`[[1,2,2,2,2],[2,2,2,2,0],[2,0,0,0,0],[0,0,2,2,2],[2,0,0,2,0]]` `5` 不转向，直走 `(0,0)→(1,1)→(2,2)→(3,3)→(4,4)`
`[[1]]` `1` 只有起点
---
参考来源
- 灵茶山艾府题解中的记忆化搜索思路
- walkccc 题解中的 C++ 实现参考
- Progiez 的 Java 实现参考