leetcode [1139] 最大的以 1 为边界的正方形

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1

思路：

碰到1的时候，往左上角寻找，如果有1，检测能否构成正方形。如果可以更新答案。

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0 or sum(sum(g) for g in grid) == 0:
            return 0

        def check(i, j, line):
            nonlocal grid
            for x in range(i - line, i + 1):
                if grid[x][j] == 0 or grid[x][j - line] == 0:
                    return False
            for y in range(j - line, j + 1):
                if grid[i][y] == 0 or grid[i - line][y] == 0:
                    return False
            return True

        ans = 1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    line = ans
                    x, y = i - line, j - line
                    while x >= 0 and y >= 0:
                        if grid[x][y] == 1 and check(i, j, line):
                            ans = line + 1
                        line = line + 1
                        x, y = i - line, j - line
        return ans**2