코너 경로의 최대 후행 0

크기가 grid인 2D 정수 배열m x n이 제공되며 각 셀에는 양의 정수가 포함됩니다.

모서리가 있는 경로는 최대 한 번 회전하는 인접한 셀 세트로 정의됩니다. 보다 구체적으로, 경로는 이전에 방문한 셀로 돌아가지 않고 턴(있는 경우)까지 수평 또는 수직으로 배타적으로 이동해야 합니다. 회전 후 경로는 다른 방향으로만 이동합니다. 이전에 방문한 셀로 돌아가지 않고 수평으로 이동한 경우 수직으로 이동하고 그 반대의 경우도 마찬가지입니다.

경로의 곱은 경로에 있는 모든 값의 곱으로 정의됩니다.
grid 에서 찾은 코너 경로의 곱에서 후행 0의 최대 개수를 반환합니다.

메모:

수평 이동은 왼쪽 또는 오른쪽 방향으로 이동하는 것을 의미합니다.

수직 이동은 위 또는 아래 방향으로 이동하는 것을 의미합니다.

예 1:



입력: 그리드 = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10, 6],[22,7,4,5,3]]
출력: 3
설명: 왼쪽의 그리드는 유효한 모퉁이 경로를 보여줍니다.
그것은 15 * 20 * 6 * 1 * 10 = 18000의 곱을 가지며 3개의 후행 0이 있습니다.
이것이 코너링된 경로의 곱에서 최대 후행 0임을 알 수 있습니다.

중간에 있는 그리드는 한 번 이상 회전하므로 코너링 경로가 아닙니다.
오른쪽의 그리드는 이전에 방문한 셀로 돌아가야 하므로 모서리가 있는 경로가 아닙니다.

예 2:



입력: 그리드 = [[4,3,2],[7,6,1],[8,8,8]]
출력: 0
설명: 그리드는 위의 그림과 같습니다.
후행 0이 있는 제품이 되는 모퉁이 경로가 그리드에 없습니다.

제약:

m == grid.length

n == grid[i].length

1 <= m, n <= 105

1 <= m * n <= 105

1 <= grid[i][j] <= 1000

해결책:

class Solution:
    def num5divs(self, num):
        t = 0
        f = 0
        while num % 5 == 0:
            num = num // 5
            f += 1
        while num % 2 == 0:
            num = num // 2
            t += 1
        return (t, f)

    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        vertprefix = [[(0, 0)] for i in range(n)]
        horprefix = [[(0, 0)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                grid[i][j] = self.num5divs(grid[i][j])
                a, b = grid[i][j]
                ha, hb = horprefix[i][-1]
                va, vb = vertprefix[j][-1]
                horprefix[i].append((ha + a, hb + b))
                vertprefix[j].append((va + a, vb + b))
        maxtrail = 0
        for i in range(m):
            for j in range(n):
                hors = [vertprefix[j][i], (vertprefix[j][-1][0] - vertprefix[j][i + 1][0], vertprefix[j][-1][1] - vertprefix[j][i + 1][1])]
                verts = [horprefix[i][j], (horprefix[i][-1][0] - horprefix[i][j + 1][0], horprefix[i][-1][1] - horprefix[i][j + 1][1])]
                for ha, hb in hors:
                    for va, vb in verts:
                        a, b = grid[i][j]
                        maxtrail = max(maxtrail, min(a + ha + va, b + hb + vb))
        return maxtrail