length-of-longest-v-shaped-diagonal-segment

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 2D integer matrix <code>grid</code> of size <code>n x m</code>, where each element is either <code>0</code>, <code>1</code>, or <code>2</code>.

A V-shaped diagonal segment is defined as:

<ul>
	<li>The segment starts with <code>1</code>.</li>
	<li>The subsequent elements follow this infinite sequence: <code>2, 0, 2, 0, ...</code>.</li>
	<li>The segment:
	<ul>
		<li>Starts along a diagonal direction (top-left to bottom-right, bottom-right to top-left, top-right to bottom-left, or bottom-left to top-right).</li>
		<li>Continues the sequence in the same diagonal direction.</li>
		<li>Makes at most one clockwise 90-degree turn to another diagonal direction while maintaining the sequence.</li>
	</ul>
	</li>
</ul>

<img alt="" src="https://assets.leetcode.com/uploads/2025/01/11/length_of_longest3.jpg" style="width: 481px; height: 202px;" />

Return the length of the longest V-shaped diagonal segment. If no valid segment exists, return 0.

&nbsp;
Example 1:

<div class="example-block">
Input: 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]]

Output: 5

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/12/09/matrix_1-2.jpg" style="width: 201px; height: 192px;" />

The longest V-shaped diagonal segment has a length of 5 and follows these coordinates: <code>(0,2) &rarr; (1,3) &rarr; (2,4)</code>, takes a 90-degree clockwise turn at <code>(2,4)</code>, and continues as <code>(3,3) &rarr; (4,2)</code>.
</div>

Example 2:

<div class="example-block">
Input: 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]]

Output: 4

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/12/09/matrix_2.jpg" style="width: 201px; height: 201px;" />

The longest V-shaped diagonal segment has a length of 4 and follows these coordinates: <code>(2,3) &rarr; (3,2)</code>, takes a 90-degree clockwise turn at <code>(3,2)</code>, and continues as <code>(2,1) &rarr; (1,0)</code>.
</div>

Example 3:

<div class="example-block">
Input: 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]]

Output: 5

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/12/09/matrix_3.jpg" style="width: 201px; height: 201px;" />

The longest V-shaped diagonal segment has a length of 5 and follows these coordinates: <code>(0,0) &rarr; (1,1) &rarr; (2,2) &rarr; (3,3) &rarr; (4,4)</code>.
</div>

Example 4:

<div class="example-block">
Input: grid = [[1]]

Output: 1

Explanation:

The longest V-shaped diagonal segment has a length of 1 and follows these coordinates: <code>(0,0)</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>m == grid[i].length</code></li>
	<li><code>1 &lt;= n, m &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code>, <code>1</code> or <code>2</code>.</li>
</ul>

lenOfVDiagonal

Length of Longest V-Shaped Diagonal Segment

Memoization

Array

Dynamic Programming

Matrix

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

V 形对角线段 定义如下：

<ul>
	<li>线段从&nbsp;<code>1</code> 开始。</li>
	<li>后续元素按照以下无限序列的模式排列：<code>2, 0, 2, 0, ...</code>。</li>
	<li>该线段：
	<ul>
		<li>起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）。</li>
		<li>沿着相同的对角方向继续，保持&nbsp;序列模式&nbsp;。</li>
		<li>在保持&nbsp;序列模式&nbsp;的前提下，最多允许&nbsp;一次顺时针 90 度转向&nbsp;另一个对角方向。</li>
	</ul>
	</li>
</ul>

<img alt="" src="https://pic.leetcode.cn/1739609732-jHpPma-length_of_longest3.jpg" style="width: 481px; height: 202px;" />

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

&nbsp;

示例 1：

<div class="example-block">
输入： 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

解释：

<img alt="" src="https://pic.leetcode.cn/1739609768-rhePxN-matrix_1-2.jpg" style="width: 201px; height: 192px;" />

最长的 V 形对角线段长度为 5，路径如下：<code>(0,2) → (1,3) → (2,4)</code>，在 <code>(2,4)</code> 处进行&nbsp;顺时针 90 度转向&nbsp;，继续路径为 <code>(3,3) → (4,2)</code>。
</div>

示例 2：

<div class="example-block">
输入： 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

解释：

<img alt="" src="https://pic.leetcode.cn/1739609774-nYJElV-matrix_2.jpg" style="width: 201px; height: 201px;" />

最长的 V 形对角线段长度为 4，路径如下：<code>(2,3) → (3,2)</code>，在 <code>(3,2)</code> 处进行&nbsp;顺时针 90 度转向&nbsp;，继续路径为 <code>(2,1) → (1,0)</code>。
</div>

示例 3：

<div class="example-block">
输入： 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

解释：

<img alt="" src="https://pic.leetcode.cn/1739609780-tlkdUW-matrix_3.jpg" style="width: 201px; height: 201px;" />

最长的 V 形对角线段长度为 5，路径如下：<code>(0,0) → (1,1) → (2,2) → (3,3) → (4,4)</code>。
</div>

示例 4：

<div class="example-block">
输入： grid = [[1]]

输出： 1

解释：

最长的 V 形对角线段长度为 1，路径如下：<code>(0,0)</code>。
</div>

&nbsp;

提示：

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>m == grid[i].length</code></li>
	<li><code>1 &lt;= n, m &lt;= 500</code></li>
	<li><code>grid[i][j]</code> 的值为 <code>0</code>、<code>1</code> 或 <code>2</code>。</li>
</ul>