Участник:Taranov srg/Largest 1 Bordered Square

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/largest-1-bordered-square

Python3

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        import numpy as np
 
        grid = np.array(grid)
        n0 = grid.shape[0]
        n1 = grid.shape[1]
        sum_along_0, sum_along_1 = np.empty_like(grid), np.empty_like(grid)
        sum_along_0[0] = grid[0]
        sum_along_1[:,0] = grid[:,0]
        for i in range(1, n0):
            sum_along_0[i] = (sum_along_0[i-1] + grid[i]) * grid[i]
        for i in range(1, n1):
            sum_along_1[:,i] = (sum_along_1[:,i-1] + grid[:,i]) * grid[:,i]
        counter = 0
        for i in range(n0-1,-1,-1):
            for j in range(n1-1,-1,-1):
                max_size = min(i,j)
                if min(sum_along_0[i,j], sum_along_1[i,j]):
                    counter = max(counter, 1)
                for c in range(min(min(sum_along_0[i,j], sum_along_1[i,j]), max_size), 0, -1):
                    if sum_along_0[i,j-c] > c and sum_along_1[i-c,j] > c:
                        counter = max(counter, c+1)
                        break
        return counter**2