安通建设有限公司网站谷歌搜索网页版入口

1139. 最大的以 1 为边界的正方形

难度中等137收藏分享切换为英文接收动态反馈

给你一个由若干 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

解题思路：以正方形周长的路径扫描每个子网格；

以当前坐标(i,j)为起点，L为边长，扫描一个正方形的周长，判断是否构成一个正方形，并不断更新maxL（当前的最大边长）；

最后返回maxL*maxL即可。

AC代码：

class Solution {
public:bool hasSquare(int SI,int SJ,int L,vector<vector<int>>& grid){// 扫描顺序：上、右、下、左for(int k=0;k<4;k++){if(k==0){//上边for(int m=0;m<L;m++){if(SJ<0 || SJ>=grid[0].size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SJ++;}}if(k==1){//右边for(int m=0;m<L;m++){if(SI<0 || SI>=grid.size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SI++;}}if(k==2){//下边for(int m=0;m<L;m++){if(SJ<0 || SJ>=grid[0].size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SJ--;}}if(k==3){//左边for(int m=0;m<L;m++){if(SI<0 || SI>=grid.size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SI--;}} }return true;}int largest1BorderedSquare(vector<vector<int>>& grid) {if(grid.size()==1){for(int i=0;i<grid[0].size();i++){if(grid[0][i]==1)return 1;}return 0;}//解题思路：以正方形周长的路径扫描每个子网格int maxL=0;int row=grid.size();    //行数int col=grid[0].size(); //列数for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]!=1)continue;int L=max(maxL,1);//以当前坐标(i,j)为起点，L为边长，扫描一个正方形的周长//判断是否构成一个正方形int LLen=min(row-i,col-j);bool isOk=false;for(;L<=LLen;L++){isOk=hasSquare(i,j,L,grid);if(isOk)maxL=max(L,maxL);} }}return maxL*maxL;}
};