Kimi LeetCode 3459. 最长 V 形对角线段的长度 C语言实现
以下是 LeetCode 3459「最长 V 形对角线段的长度」的 C 语言实现。
解题思路
核心算法：记忆化搜索 (DFS + Memoization)
- 状态定义：`memo[i][j][dir][turn]` 表示从坐标 `(i,j)` 出发，当前移动方向为 `dir`，是否还能右转（`turn`）的情况下，后续路径的最大长度。
- 四个对角方向（按顺时针排列）：
- `dir=0`: (1, 1) 右下
- `dir=1`: (1, -1) 左下
- `dir=2`: (-1, -1) 左上
- `dir=3`: (-1, 1) 右上
- 顺时针90度右转：`(dir + 1) % 4`
- 序列模式：`1 → 2 → 0 → 2 → 0 → ...`，下一个目标值用 `2 - target` 计算
复杂度：
- 时间：O(n × m × 4 × 2) = O(n × m)
- 空间：O(n × m × 4 × 2) = O(n × m)
---
C 代码
```c
#include <stdlib.h>
/**
* LeetCode 3459. 最长 V 形对角线段的长度 - C语言实现
* =====================================================
*
* 题目要求：
* 在 n x m 的矩阵中，找最长的 V 形对角线段。
* - 起点必须是 1
* - 后续值按 2, 0, 2, 0, ... 交替
* - 沿对角线方向移动
* - 最多允许一次顺时针 90 度转向
*
* 算法：记忆化搜索 (DFS + Memoization)
*/
// 四个对角方向（按顺时针排列）：右下、左下、左上、右上
static const int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
// 扁平化访问记忆化数组：memo[i][j][dir][turn]
// 索引计算：(i * n + j) * 8 + dir * 2 + turn
static inline int* get_memo(int *memo, int n, int i, int j, int dir, int turn) {
return &memo[(i * n + j) * 8 + dir * 2 + turn];
}
/**
* DFS 搜索从 (i,j) 沿方向 dir 前进，期望值为 target 的最长路径
* @param turn: 1 表示还可以右转，0 表示已经转过或不能转
* @return: 从下一个合法格子开始的路径长度（不含当前(i,j)）
*/
int dfs(int **grid, int *memo, int m, int n, int i, int j, int dir, int turn, int target) {
int ni = i + DIRS[dir][0];
int nj = j + DIRS[dir][1];
// 越界或值不匹配，路径终止
if (ni < 0 || ni >= m || nj < 0 || nj >= n || grid[ni][nj] != target) {
return 0;
}
// 查记忆化表
int *p = get_memo(memo, n, ni, nj, dir, turn);
if (*p != 0) {
return *p;
}
int next_target = 2 - target; // 2->0, 0->2
// 选择1：继续沿当前方向直行
int res = dfs(grid, memo, m, n, ni, nj, dir, turn, next_target) + 1;
// 选择2：如果还能右转，顺时针90度转向（dir -> (dir+1)%4）
if (turn) {
int turn_res = dfs(grid, memo, m, n, ni, nj, (dir + 1) % 4, 0, next_target) + 1;
if (turn_res > res) {
res = turn_res;
}
}
*p = res;
return res;
}
int lenOfVDiagonal(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
if (m == 0 || n == 0) {
return 0;
}
// 分配并初始化记忆化数组（全部置0）
// 每个格子8种状态：4方向 x 2种turn状态
int *memo = (int *)calloc(m * n * 8, sizeof(int));
int ans = 0;
// 遍历所有可能的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 起点必须是 1
if (grid[i][j] != 1) {
continue;
}
// 尝试四个初始方向
for (int dir = 0; dir < 4; dir++) {
// dfs返回从(i,j)之后的路径长度，+1包含起点本身
int len = dfs(grid, memo, m, n, i, j, dir, 1, 2) + 1;
if (len > ans) {
ans = len;
}
}
}
}
free(memo);
return ans;
}
```
---
关键要点说明
要点 说明
方向数组顺序 必须按顺时针排列 `(右下→左下→左上→右上)`，这样 `(dir+1)%4` 才是正确的顺时针90度转向
目标值交替 `next_target = 2 - target` 巧妙实现 `2↔0` 交替
记忆化状态 每个格子 8 种状态（4方向 × 2种turn），用扁平化数组存储减少分配开销
起点处理 只有值为 `1` 的格子才能作为起点，初始目标值固定为 `2`
下载文件：[leetcode_3459.c](sandbox:///mnt/agents/output/leetcode_3459.c)