1139. 最大的以 1 为边界的正方形
难度中等
给你一个由若干 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.0（已看题解）：
（1）自己思考的时候就发现最大正方形的判断只能从它的四条边下手，但推不出dp子结构。题解里大佬就是对边定义dp： dp[i][j][0]：点[i][j]左边连续的 1的数量 dp[i][j][0]=dp[i-1][j][0]+1 dp[i][j][1]：点[i][j]上边连续的 1的数量 dp[i][j][1]=dp[i][j-1][1]+1 以点[i][j]为右下角的最大正方形的边长side为 min(dp[i][j][0],dp[i][j][1])，然后检查该最大正方形的两个邻接点，它们另一个方向的连续边长是否大于等于side（side可从大到小遍历）。 （2）记录最大正方形的边长数max_n，在遍历二维dp数组时碰到min(dp[i][j][0],dp[i][j][1])小于max_n时，即可跳过不检查了。
代码1.0（已完成）：
class Solution {
public:
int largest1BorderedSquare(vector
<vector
<int>>& grid
) {
int row
= grid
.size(), col
= grid
[0].size();
vector
<vector
<vector
<int>>> dp(row
+ 1, vector
<vector
<int>>(col
+ 1, vector<int>(2, 0)));
for (int i
= 1; i
<= row
; ++i
)
{
for (int j
= 1; j
<= col
; ++j
)
{
if (grid
[i
- 1][j
- 1])
{
dp
[i
][j
][0] = dp
[i
][j
-1][0] + 1;
dp
[i
][j
][1] = dp
[i
-1][j
][1] + 1;
}
}
}
int max_n
= 0;
for (int i
= row
; i
>= 1; --i
)
{
for (int j
= col
; j
>= 1; --j
)
{
int side
= min(dp
[i
][j
][0], dp
[i
][j
][1]);
if (side
<= max_n
) continue;
for (; side
>= 1; --side
)
{
if (dp
[i
][j
- side
+ 1][1] >= side
)
{
if (dp
[i
- side
+1][j
][0] >= side
)
{
max_n
=max(max_n
,side
);
}
}
}
}
}
return pow(max_n
, 2);
}
};
