以下是 LeetCode 3459「最长 V 形对角线段的长度」的 C 语言实现。解题思路核心算法记忆化搜索 (DFS Memoization)- 状态定义memo[i][j][dir][turn] 表示从坐标 (i,j) 出发当前移动方向为 dir是否还能右转turn的情况下后续路径的最大长度。- 四个对角方向按顺时针排列- dir0: (1, 1) 右下- dir1: (1, -1) 左下- dir2: (-1, -1) 左上- dir3: (-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 turnstatic 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 - (dir1)%4if (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) {// 起点必须是 1if (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;}---关键要点说明要点 说明方向数组顺序 必须按顺时针排列 (右下→左下→左上→右上)这样 (dir1)%4 才是正确的顺时针90度转向目标值交替 next_target 2 - target 巧妙实现 2↔0 交替记忆化状态 每个格子 8 种状态4方向 × 2种turn用扁平化数组存储减少分配开销起点处理 只有值为 1 的格子才能作为起点初始目标值固定为 2下载文件[leetcode_3459.c](sandbox:///mnt/agents/output/leetcode_3459.c)