Longest Diagonal Segment with at Most One Clockwise Turn

### Problem You are given an `n` by `m` matrix `grid` containing only `0`, `1`, and `2`. Find the longest diagonal segment with these properties: - Its first cell contains `1`. - Its later cells contain `2, 0, 2, 0, ...`, in that order. - Each step moves to a diagonally adjacent cell. The segment starts in any of the four diagonal directions and may continue straight or make **at most one clockwise 90-degree turn**. The value sequence continues across the turn. With rows increasing downward and columns increasing rightward, the clockwise direction cycle is down-right, down-left, up-left, up-right, then down-right again. A counterclockwise turn is not permitted. Return the greatest number of cells in a valid segment. A single cell containing `1` is valid. If no valid segment exists, return `0`. ```cpp class Solution { public: int lenOfVDiagonal(vector<vector<int>>& grid); }; ``` ### Examples **Example 1:** ```text Input: grid = [[2,1,2,2],[2,2,2,2],[2,0,2,2]] Output: 3 Explanation: Follow (0,1) -> (1,2) -> (2,1), with values 1,2,0. The down-right direction turns clockwise to down-left at (1,2). The only starting 1 has no valid segment longer than three cells. ``` **Example 2:** ```text Input: grid = [[1,2,0],[2,2,2],[2,2,2]] Output: 2 Explanation: The segment (0,0) -> (1,1) has values 1,2. Its next straight or clockwise cell contains 2 instead of the required 0. Reaching the 0 at (0,2) would require a counterclockwise turn, so that three-cell path is invalid. ``` ### Constraints - `n == grid.length` and `m == grid[i].length`. - `1 <= n, m <= 500`. - Every `grid[i][j]` is `0`, `1`, or `2`. ### Clarifying Questions - Must the segment turn? No. Zero turns are allowed. - Can a later cell contain another `1`? No. After the first cell, the values alternate between `2` and `0`. - Is the turning cell counted twice? No. Length counts visited cells, with the turning cell counted once. - Does the answer require the path coordinates? No, return only its maximum length. ### What a Strong Answer Covers - Preserves the starting value, subsequent value order, and allowed diagonal moves. - Enforces the clockwise direction and the limit of one turn. - Explains why all possible starting cells and legal turn positions are covered. - Handles no starting `1`, a single-cell segment, rectangular matrices, and the full matrix size. ### Follow-up Questions - Why can allowing both turn directions change the result? - What result is possible when the matrix has only one row or one column? ```hint Separate what remains after turning Once a turn has been used, the rest of the segment must continue in one fixed diagonal direction. Consider how to reuse the lengths of such straight continuations. ```