Hard

题目描述

给你一个大小为 n x m 的二维整数矩阵 grid，其中每个元素都是 0、1 或 2。

V 形对角线段定义如下：

  • 段以 1 开始
  • 后续元素遵循这个无限序列：2, 0, 2, 0, …
  • 段的移动规则：
    • 沿着对角线方向开始（左上到右下，右下到左上，右上到左下，或左下到右上）
    • 在同一对角线方向上继续序列
    • 最多进行一次顺时针 90 度转弯到另一个对角线方向，同时保持序列

返回最长 V 形对角线段的长度。如果不存在有效段，返回 0。

示例 1：

输入：grid = [[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
解释：最长的 V 形对角线段长度为 5，坐标路径为：(0,2) → (1,3) → (2,4)，在 (2,4) 处顺时针转弯 90 度，然后继续 (3,3) → (4,2)。

示例 2：

输入：grid = [[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

示例 3：

输入：grid = [[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

示例 4：

输入：grid = [[1]]
输出：1

约束条件：

  • n == grid.length
  • m == grid[i].length
  • 1 <= n, m <= 500
  • grid[i][j] 是 0、1 或 2

解题思路

解题思路

这是一道复杂的动态规划问题，需要处理 V 形对角线段的路径搜索。

核心思路：

  1. 状态定义：使用记忆化搜索，状态为 (row, col, direction, hasTurned, step)，其中：

    • (row, col) 表示当前位置
    • direction 表示当前移动方向（0-3 代表四个对角线方向）
    • hasTurned 表示是否已经转弯
    • step 表示当前在序列中的位置

  2. 序列规则：段必须以 1 开始，然后按照 2, 0, 2, 0… 的模式继续。我们可以用 step 来判断当前应该是什么数字。

  3. 方向转换：四个对角线方向分别是：

    • 0: 右下 (1, 1)
    • 1: 左下 (1, -1)
    • 2: 左上 (-1, -1)
    • 3: 右上 (-1, 1)

    顺时针转弯就是方向编号加1（模4）。

  4. 搜索策略：

    • 从每个值为 1 的位置开始 DFS
    • 对于每个位置，尝试继续当前方向或进行转弯（如果还没转过弯）
    • 使用记忆化避免重复计算

  5. 优化：使用记忆化搜索减少重复计算，状态空间为 O(n×m×4×2×2)。

推荐解法是记忆化搜索，因为它能够有效处理复杂的状态转移，同时避免重复计算。

代码实现

class Solution {
public:
    vector<vector<int>> dirs = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
    map<tuple<int, int, int, bool, int>, int> memo;
    
    int dfs(vector<vector<int>>& grid, int row, int col, int dir, bool turned, int step) {
        int n = grid.size(), m = grid[0].size();
        
        if (row < 0 || row >= n || col < 0 || col >= m) return 0;
        
        // Check expected value
        int expected = (step == 0) ? 1 : ((step % 2 == 1) ? 2 : 0);
        if (grid[row][col] != expected) return 0;
        
        auto key = make_tuple(row, col, dir, turned, step);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        int result = 1; // Current cell counts
        int maxLen = 1;
        
        // Continue in same direction
        int nr = row + dirs[dir][0];
        int nc = col + dirs[dir][1];
        maxLen = max(maxLen, 1 + dfs(grid, nr, nc, dir, turned, step + 1));
        
        // Try turning (only once)
        if (!turned) {
            int newDir = (dir + 1) % 4;
            nr = row + dirs[newDir][0];
            nc = col + dirs[newDir][1];
            maxLen = max(maxLen, 1 + dfs(grid, nr, nc, newDir, true, step + 1));
        }
        
        return memo[key] = maxLen;
    }
    
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int dir = 0; dir < 4; dir++) {
                        result = max(result, dfs(grid, i, j, dir, false, 0));
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]
        memo = {}
        
        def dfs(row, col, direction, turned, step):
            if row < 0 or row >= n or col < 0 or col >= m:
                return 0
            
            # Check expected value
            expected = 1 if step == 0 else (2 if step % 2 == 1 else 0)
            if grid[row][col] != expected:
                return 0
            
            key = (row, col, direction, turned, step)
            if key in memo:
                return memo[key]
            
            max_len = 1  # Current cell counts
            
            # Continue in same direction
            dr, dc = dirs[direction]
            nr, nc = row + dr, col + dc
            max_len = max(max_len, 1 + dfs(nr, nc, direction, turned, step + 1))
            
            # Try turning (only once)
            if not turned:
                new_dir = (direction + 1) % 4
                dr, dc = dirs[new_dir]
                nr, nc = row + dr, col + dc
                max_len = max(max_len, 1 + dfs(nr, nc, new_dir, True, step + 1))
            
            memo[key] = max_len
            return max_len
        
        result = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    for direction in range(4):
                        result = max(result, dfs(i, j, direction, False, 0))
        
        return result

public class Solution {
    private int[][] dirs = new int[][] {
        new int[] {1, 1}, new int[] {1, -1}, 
        new int[] {-1, -1}, new int[] {-1, 1}
    };
    private Dictionary<(int, int, int, bool, int), int> memo = new Dictionary<(int, int, int, bool, int), int>();
    
    private int Dfs(int[][] grid, int row, int col, int dir, bool turned, int step) {
        int n = grid.Length, m = grid[0].Length;
        
        if (row < 0 || row >= n || col < 0 || col >= m) return 0;
        
        // Check expected value
        int expected = (step == 0) ? 1 : ((step % 2 == 1) ? 2 : 0);
        if (grid[row][col] != expected) return 0;
        
        var key = (row, col, dir, turned, step);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        int maxLen = 1; // Current cell counts
        
        // Continue in same direction
        int nr = row + dirs[dir][0];
        int nc = col + dirs[dir][1];
        maxLen = Math.Max(maxLen, 1 + Dfs(grid, nr, nc, dir, turned, step + 1));
        
        // Try turning (only once)
        if (!turned) {
            int newDir = (dir + 1) % 4;
            nr = row + dirs[newDir][0];
            nc = col + dirs[newDir][1];
            maxLen = Math.Max(maxLen, 1 + Dfs(grid, nr, nc, newDir, true, step + 1));
        }
        
        memo[key] = maxLen;
        return maxLen;
    }
    
    public int LenOfVDiagonal(int[][] grid) {
        int n = grid.Length, m = grid[0].Length;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int dir = 0; dir < 4; dir++) {
                        result = Math.Max(result, Dfs(grid, i, j, dir, false, 0));
                    }
                }
            }
        }
        
        return result;
    }
}

var lenOfVDiagonal = function(grid) {
    const n = grid.length;
    const m = grid[0].length;
    
    const directions = [
        [-1, -1], // top-left
        [-1, 1],  // top-right
        [1, 1],   // bottom-right
        [1, -1]   // bottom-left
    ];
    
    const clockwiseNext = [1, 2, 3, 0];
    
    function isValid(r, c) {
        return r >= 0 && r < n && c >= 0 && c < m;
    }
    
    function getExpectedValue(pos) {
        if (pos === 0) return 1;
        return pos % 2 === 1 ? 2 : 0;
    }
    
    let maxLength = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] !== 1) continue;
            
            for (let dir = 0; dir < 4; dir++) {
                let r = i, c = j;
                let pos = 0;
                let length = 0;
                let currentDir = dir;
                let hasTurned = false;
                
                while (isValid(r, c) && grid[r][c] === getExpectedValue(pos)) {
                    length++;
                    pos++;
                    
                    let nextR = r + directions[currentDir][0];
                    let nextC = c + directions[currentDir][1];
                    
                    if (isValid(nextR, nextC) && grid[nextR][nextC] === getExpectedValue(pos)) {
                        r = nextR;
                        c = nextC;
                    } else if (!hasTurned) {
                        let newDir = clockwiseNext[currentDir];
                        let turnR = r + directions[newDir][0];
                        let turnC = c + directions[newDir][1];
                        
                        if (isValid(turnR, turnC) && grid[turnR][turnC] === getExpectedValue(pos)) {
                            hasTurned = true;
                            currentDir = newDir;
                            r = turnR;
                            c = turnC;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                
                maxLength = Math.max(maxLength, length);
            }
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m × 4 × 2 × L)，其中 L 是最长可能路径长度，最坏情况下为 O(n × m)
空间复杂度O(n × m × 4 × 2 × L)，记忆化存储的状态空间