1139. Largest 1-Bordered Square

题目信息

题号:

1139

难度:

Medium

主题:

二进制矩阵、正方形边框、动态规划

原题:

LeetCode 1139

重点:

正方形四条边必须全部为 1,内部格可以为 0 或 1;返回最大正方形面积,不存在时返回 0

题目重述

给定只包含 0 和 1 的矩阵 grid。寻找一个行列范围连续且边长相等的正方形子矩阵,使其顶部、底部、左侧和右侧边框上的所有格子都为 1。

正方形内部的格子没有限制。请返回满足条件的最大正方形面积;若连边长为 1 的全 1 正方形也不存在,返回 0。

1 <= grid.length, grid[i].length <= 100,每个格子为 0 或 1。

自建示例

左上角存在边长为二的完整边框:

输入:grid = [[1,1,0],[1,1,0],[0,0,0]]
输出:4
解释:左上角 2 x 2 子矩阵的四条边均为 1,面积为 4;不存在更大的合法正方形。

矩阵没有任何一:

输入:grid = [[0,0],[0,0]]
输出:0
解释:不存在边长为 1 的全 1 正方形,因此返回 0。