LeetCode 3459: Length of Longest V-Shaped Diagonal Segment (Diagonal DFS + Memoization)
LeetCode 3459MatrixDPToday we solve LeetCode 3459 - Length of Longest V-Shaped Diagonal Segment.
Source: https://leetcode.com/problems/length-of-longest-v-shaped-diagonal-segment/
English
Problem Summary
Given an n x m grid containing only 0, 1, 2, a valid segment must start from 1, then follow diagonal cells with value pattern 2,0,2,0,.... You may move along one diagonal direction and optionally make at most one clockwise 90° turn to another diagonal direction. Return the maximum length.
Key Idea
This is a path DP on a tiny state space. At each cell we only care about:
1) current cell (r,c)
2) current diagonal direction dir
3) whether we already turned clockwise (turned)
4) next required value (2 or 0)
From one state, we try two transitions: go straight, or (if not turned yet) turn to clockwise diagonal once. Memoization makes each state computed once.
Diagonal Direction Order
Use clockwise order on diagonals:
0: (-1,+1) (NE), 1: (+1,+1) (SE), 2: (+1,-1) (SW), 3: (-1,-1) (NW).
Then clockwise turn is (dir + 1) % 4.
Algorithm
1) Enumerate every cell with value 1 as start.
2) For each start and each of 4 directions, run DFS state dfs(r,c,dir,0,2).
3) DFS returns max path length starting at current cell (including current cell).
4) Transition to next cell only when in-bounds and equal to required next value.
5) Next required value toggles: 2 -> 0, 0 -> 2.
6) Take global maximum.
Complexity
States: n * m * 4 * 2 * 2, each with constant transitions, so total O(nm). Space O(nm) for memoization.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
private int n, m;
private int[][] grid;
private int[] dr = {-1, 1, 1, -1};
private int[] dc = {1, 1, -1, -1};
private int[][][][][] memo; // r,c,dir,turned,nextIdx(0->expect2,1->expect0)
public int lenOfVDiagonal(int[][] grid) {
this.grid = grid;
n = grid.length;
m = grid[0].length;
memo = new int[n][m][4][2][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int d = 0; d < 4; d++) {
for (int t = 0; t < 2; t++) {
Arrays.fill(memo[i][j][d][t], -1);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 1) continue;
for (int d = 0; d < 4; d++) {
ans = Math.max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
}
private int dfs(int r, int c, int dir, int turned, int nextIdx) {
if (memo[r][c][dir][turned][nextIdx] != -1) {
return memo[r][c][dir][turned][nextIdx];
}
int need = (nextIdx == 0) ? 2 : 0;
int best = 1;
int nr = r + dr[dir], nc = c + dc[dir];
if (in(nr, nc) && grid[nr][nc] == need) {
best = Math.max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned == 0) {
int nd = (dir + 1) % 4;
nr = r + dr[nd];
nc = c + dc[nd];
if (in(nr, nc) && grid[nr][nc] == need) {
best = Math.max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
memo[r][c][dir][turned][nextIdx] = best;
return best;
}
private boolean in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
}func lenOfVDiagonal(grid [][]int) int {
n, m := len(grid), len(grid[0])
dr := []int{-1, 1, 1, -1}
dc := []int{1, 1, -1, -1}
memo := make([][][][][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([][][][]int, m)
for j := 0; j < m; j++ {
memo[i][j] = make([][][]int, 4)
for d := 0; d < 4; d++ {
memo[i][j][d] = make([][]int, 2)
for t := 0; t < 2; t++ {
memo[i][j][d][t] = []int{-1, -1}
}
}
}
}
in := func(r, c int) bool {
return r >= 0 && r < n && c >= 0 && c < m
}
var dfs func(r, c, dir, turned, nextIdx int) int
dfs = func(r, c, dir, turned, nextIdx int) int {
if memo[r][c][dir][turned][nextIdx] != -1 {
return memo[r][c][dir][turned][nextIdx]
}
need := 2
if nextIdx == 1 {
need = 0
}
best := 1
nr, nc := r+dr[dir], c+dc[dir]
if in(nr, nc) && grid[nr][nc] == need {
v := 1 + dfs(nr, nc, dir, turned, nextIdx^1)
if v > best {
best = v
}
}
if turned == 0 {
nd := (dir + 1) % 4
nr, nc = r+dr[nd], c+dc[nd]
if in(nr, nc) && grid[nr][nc] == need {
v := 1 + dfs(nr, nc, nd, 1, nextIdx^1)
if v > best {
best = v
}
}
}
memo[r][c][dir][turned][nextIdx] = best
return best
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] != 1 {
continue
}
for d := 0; d < 4; d++ {
v := dfs(i, j, d, 0, 0)
if v > ans {
ans = v
}
}
}
}
return ans
}class Solution {
public:
int lenOfVDiagonal(vector>& grid) {
int n = grid.size(), m = grid[0].size();
int dr[4] = {-1, 1, 1, -1};
int dc[4] = {1, 1, -1, -1};
// memo[r][c][dir][turned][nextIdx]
vector memo(n, vector(m, vector(4, vector(2, vector(2, -1)))));
auto in = [&](int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
};
function dfs = [&](int r, int c, int dir, int turned, int nextIdx) {
int &res = memo[r][c][dir][turned][nextIdx];
if (res != -1) return res;
int need = (nextIdx == 0 ? 2 : 0);
int best = 1;
int nr = r + dr[dir], nc = c + dc[dir];
if (in(nr, nc) && grid[nr][nc] == need) {
best = max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned == 0) {
int nd = (dir + 1) % 4;
nr = r + dr[nd], nc = c + dc[nd];
if (in(nr, nc) && grid[nr][nc] == need) {
best = max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
return res = best;
};
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 1) continue;
for (int d = 0; d < 4; d++) {
ans = max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
}
}; from functools import lru_cache
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)] # NE, SE, SW, NW (clockwise)
def inside(r: int, c: int) -> bool:
return 0 <= r < n and 0 <= c < m
@lru_cache(None)
def dfs(r: int, c: int, d: int, turned: int, next_idx: int) -> int:
need = 2 if next_idx == 0 else 0
best = 1
dr, dc = dirs[d]
nr, nc = r + dr, c + dc
if inside(nr, nc) and grid[nr][nc] == need:
best = max(best, 1 + dfs(nr, nc, d, turned, next_idx ^ 1))
if turned == 0:
nd = (d + 1) % 4
dr2, dc2 = dirs[nd]
nr2, nc2 = r + dr2, c + dc2
if inside(nr2, nc2) and grid[nr2][nc2] == need:
best = max(best, 1 + dfs(nr2, nc2, nd, 1, next_idx ^ 1))
return best
ans = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
for d in range(4):
ans = max(ans, dfs(i, j, d, 0, 0))
return ansvar lenOfVDiagonal = function(grid) {
const n = grid.length, m = grid[0].length;
const dr = [-1, 1, 1, -1];
const dc = [1, 1, -1, -1];
const inside = (r, c) => r >= 0 && r < n && c >= 0 && c < m;
const memo = new Map();
function dfs(r, c, dir, turned, nextIdx) {
const key = `${r},${c},${dir},${turned},${nextIdx}`;
if (memo.has(key)) return memo.get(key);
const need = nextIdx === 0 ? 2 : 0;
let best = 1;
let nr = r + dr[dir], nc = c + dc[dir];
if (inside(nr, nc) && grid[nr][nc] === need) {
best = Math.max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned === 0) {
const nd = (dir + 1) % 4;
nr = r + dr[nd];
nc = c + dc[nd];
if (inside(nr, nc) && grid[nr][nc] === need) {
best = Math.max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
memo.set(key, best);
return best;
}
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] !== 1) continue;
for (let d = 0; d < 4; d++) {
ans = Math.max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
};中文
题目概述
给定只包含 0/1/2 的矩阵 grid。合法线段必须从 1 开始，后续值按 2,0,2,0,... 交替，沿对角线前进，且最多只能进行一次顺时针 90° 转向。求最长长度。
核心思路
把问题建模为“小状态搜索 + 记忆化”。一个状态由 5 个维度确定：
1）当前位置 (r,c)
2）当前对角方向 dir
3）是否已经转向 turned
4）下一格要求的值（2 或 0）
5）当前格默认已计入长度
每一步最多两种决策：继续直走；或在还没转向时，执行一次顺时针转向再走。状态总数是 O(nm) 级别，记忆化后效率稳定。
方向定义
按顺时针定义 4 个对角方向：
0: (-1,+1)（右上），1: (+1,+1)（右下），2: (+1,-1)（左下），3: (-1,-1)（左上）。
顺时针转向就是 (dir + 1) % 4。
算法步骤
1）枚举所有值为 1 的格子作为起点。
2）每个起点尝试 4 个初始方向，进入 dfs(i,j,dir,0,2)（下一格应为 2）。
3）DFS 返回从当前格开始（含当前格）能走出的最大长度。
4）若下一格越界或值不匹配，就不能扩展；否则递归并切换下一个期望值（2 和 0 交替）。
5）若尚未转向，可额外尝试一次顺时针转向分支。
6）全局取最大值。
复杂度分析
状态规模是 n * m * 4 * 2 * 2，每个状态只做常数次转移，时间复杂度 O(nm)，空间复杂度 O(nm)（记忆化表）。
参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
private int n, m;
private int[][] grid;
private int[] dr = {-1, 1, 1, -1};
private int[] dc = {1, 1, -1, -1};
private int[][][][][] memo;
public int lenOfVDiagonal(int[][] grid) {
this.grid = grid;
n = grid.length;
m = grid[0].length;
memo = new int[n][m][4][2][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int d = 0; d < 4; d++) {
for (int t = 0; t < 2; t++) {
Arrays.fill(memo[i][j][d][t], -1);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 1) continue;
for (int d = 0; d < 4; d++) {
ans = Math.max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
}
private int dfs(int r, int c, int dir, int turned, int nextIdx) {
if (memo[r][c][dir][turned][nextIdx] != -1) {
return memo[r][c][dir][turned][nextIdx];
}
int need = (nextIdx == 0) ? 2 : 0;
int best = 1;
int nr = r + dr[dir], nc = c + dc[dir];
if (in(nr, nc) && grid[nr][nc] == need) {
best = Math.max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned == 0) {
int nd = (dir + 1) % 4;
nr = r + dr[nd];
nc = c + dc[nd];
if (in(nr, nc) && grid[nr][nc] == need) {
best = Math.max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
memo[r][c][dir][turned][nextIdx] = best;
return best;
}
private boolean in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
}func lenOfVDiagonal(grid [][]int) int {
n, m := len(grid), len(grid[0])
dr := []int{-1, 1, 1, -1}
dc := []int{1, 1, -1, -1}
memo := make([][][][][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([][][][]int, m)
for j := 0; j < m; j++ {
memo[i][j] = make([][][]int, 4)
for d := 0; d < 4; d++ {
memo[i][j][d] = make([][]int, 2)
for t := 0; t < 2; t++ {
memo[i][j][d][t] = []int{-1, -1}
}
}
}
}
in := func(r, c int) bool {
return r >= 0 && r < n && c >= 0 && c < m
}
var dfs func(r, c, dir, turned, nextIdx int) int
dfs = func(r, c, dir, turned, nextIdx int) int {
if memo[r][c][dir][turned][nextIdx] != -1 {
return memo[r][c][dir][turned][nextIdx]
}
need := 2
if nextIdx == 1 {
need = 0
}
best := 1
nr, nc := r+dr[dir], c+dc[dir]
if in(nr, nc) && grid[nr][nc] == need {
v := 1 + dfs(nr, nc, dir, turned, nextIdx^1)
if v > best {
best = v
}
}
if turned == 0 {
nd := (dir + 1) % 4
nr, nc = r+dr[nd], c+dc[nd]
if in(nr, nc) && grid[nr][nc] == need {
v := 1 + dfs(nr, nc, nd, 1, nextIdx^1)
if v > best {
best = v
}
}
}
memo[r][c][dir][turned][nextIdx] = best
return best
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] != 1 {
continue
}
for d := 0; d < 4; d++ {
v := dfs(i, j, d, 0, 0)
if v > ans {
ans = v
}
}
}
}
return ans
}class Solution {
public:
int lenOfVDiagonal(vector>& grid) {
int n = grid.size(), m = grid[0].size();
int dr[4] = {-1, 1, 1, -1};
int dc[4] = {1, 1, -1, -1};
vector memo(n, vector(m, vector(4, vector(2, vector(2, -1)))));
auto in = [&](int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
};
function dfs = [&](int r, int c, int dir, int turned, int nextIdx) {
int &res = memo[r][c][dir][turned][nextIdx];
if (res != -1) return res;
int need = (nextIdx == 0 ? 2 : 0);
int best = 1;
int nr = r + dr[dir], nc = c + dc[dir];
if (in(nr, nc) && grid[nr][nc] == need) {
best = max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned == 0) {
int nd = (dir + 1) % 4;
nr = r + dr[nd], nc = c + dc[nd];
if (in(nr, nc) && grid[nr][nc] == need) {
best = max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
return res = best;
};
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 1) continue;
for (int d = 0; d < 4; d++) {
ans = max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
}
}; from functools import lru_cache
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)]
def inside(r: int, c: int) -> bool:
return 0 <= r < n and 0 <= c < m
@lru_cache(None)
def dfs(r: int, c: int, d: int, turned: int, next_idx: int) -> int:
need = 2 if next_idx == 0 else 0
best = 1
dr, dc = dirs[d]
nr, nc = r + dr, c + dc
if inside(nr, nc) and grid[nr][nc] == need:
best = max(best, 1 + dfs(nr, nc, d, turned, next_idx ^ 1))
if turned == 0:
nd = (d + 1) % 4
dr2, dc2 = dirs[nd]
nr2, nc2 = r + dr2, c + dc2
if inside(nr2, nc2) and grid[nr2][nc2] == need:
best = max(best, 1 + dfs(nr2, nc2, nd, 1, next_idx ^ 1))
return best
ans = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
for d in range(4):
ans = max(ans, dfs(i, j, d, 0, 0))
return ansvar lenOfVDiagonal = function(grid) {
const n = grid.length, m = grid[0].length;
const dr = [-1, 1, 1, -1];
const dc = [1, 1, -1, -1];
const inside = (r, c) => r >= 0 && r < n && c >= 0 && c < m;
const memo = new Map();
function dfs(r, c, dir, turned, nextIdx) {
const key = `${r},${c},${dir},${turned},${nextIdx}`;
if (memo.has(key)) return memo.get(key);
const need = nextIdx === 0 ? 2 : 0;
let best = 1;
let nr = r + dr[dir], nc = c + dc[dir];
if (inside(nr, nc) && grid[nr][nc] === need) {
best = Math.max(best, 1 + dfs(nr, nc, dir, turned, nextIdx ^ 1));
}
if (turned === 0) {
const nd = (dir + 1) % 4;
nr = r + dr[nd];
nc = c + dc[nd];
if (inside(nr, nc) && grid[nr][nc] === need) {
best = Math.max(best, 1 + dfs(nr, nc, nd, 1, nextIdx ^ 1));
}
}
memo.set(key, best);
return best;
}
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] !== 1) continue;
for (let d = 0; d < 4; d++) {
ans = Math.max(ans, dfs(i, j, d, 0, 0));
}
}
}
return ans;
};
Comments