aboutsummaryrefslogtreecommitdiff
path: root/length_longest_vshape_diag_seg.py
blob: bd7c87515dec87ddce603fffca102975af2d01c0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# 3459. Length of Longest V-Shaped Diagonal Segment

"""
you are given a 2d integer matrix 'grid' of size 'n x m', where each element
is either 0, 1, or 2. a v-shaped diagonal segment is defined as: the segment
starts with 1, the subsequent elements follow this infinite sequence '2, 0,
2, 0, ...', the segment starts along a diagonal direction, the segment
continues the sequence in the same diagonal direction, and the segment makes
at most one clockwise 90-degree turn to another diagonal direction while
maintaining the sequence.
"""


class Solution(object):
    def lenOfVDiagonal(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        ds = [[1, 1], [1, -1], [-1, -1], [-1, 1]]
        nx = [2, 2, 0]
        ans, n, m = 0, len(grid), len(grid[0])

        def dp(i, j, x, d, k):
            if not (0 <= i < n and 0 <= j < m):
                return 0
            if grid[i][j] != x:
                return 0
            res = dp(i + ds[d][0], j + ds[d][1], nx[x], d, k) + 1
            if k > 0:
                d2 = (d + 1) % 4
                res2 = dp(i + ds[d2][0], j + ds[d2][1], nx[x], d2, 0) + 1
                res = max(res, res2)
            return res

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    curr = max(dp(i, j, 1, d, 1) for d in range(4))
                    ans = max(ans, curr)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.lenOfVDiagonal(
            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],
            ]
        )
    )
    print(
        obj.lenOfVDiagonal(
            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],
            ]
        )
    )
    print(
        obj.lenOfVDiagonal(
            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],
            ]
        )
    )