Length of Longest V-Shaped Diagonal Segment
Real-world version: The Longest Bend Across the MosaicThe statement here is our own: the same inputs, outputs and technique.
A mosaic mosaic holds only the marks 0, 1 and 2.
A bend is a run of tiles where each tile after the first sits diagonally beside the one before it, so one row up or down together with one column left or right. A bend has to satisfy all of the following:
- The first tile is marked
1. - The marks after it run
2,0,2,0and onwards without end. - Every step goes in the same diagonal direction, except that the run may change direction once, and only by turning a quarter turn clockwise.
The four diagonal directions in clockwise order are down-and-right, down-and-left, up-and-left, up-and-right, and then back round to down-and-right. A quarter turn clockwise moves from one to the next in that cycle.
A single tile marked 1 is a bend of length one. Return the length of the longest bend, or 0 when the mosaic holds no 1 at all.
Examples
Example 1
- Input
- mosaic = [[0, 0, 1, 0], [0, 0, 0, 2], [0, 0, 0, 0], [0, 2, 0, 0]]
- Output
- 4
The only 1 sits in the top row. Stepping down and right onto the 2, then turning a quarter turn clockwise to run down and left through the 0 and the 2, gives four tiles. Without the turn the run leaves the mosaic after two.
Example 2
- Input
- mosaic = [[1, 0, 0], [0, 2, 0], [0, 0, 0]]
- Output
- 3
From the 1 in the corner the run reaches the 2 and then the 0 going down and right, three tiles in all. Turning at the 2 reaches the other 0 instead, which is no longer.
Example 3
- Input
- mosaic = [[1, 1], [1, 1]]
- Output
- 1
Every tile is marked 1, so no run can take a second step, and a lone 1 counts as a bend of one.
Constraints
- 1 <= mosaic.length <= 500
- 1 <= mosaic[i].length <= 500
- mosaic[i][j] is 0, 1 or 2
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def len_of_v_diagonal(mosaic: list[list[int]]) -> int:public int lenOfVDiagonal(int[][] mosaic)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's