题解 | #边界都是1的最大正方形大小#

//本题首先对矩阵进行预处理
//申请一个同样大小的预处理数组
//数组的每一个位置有两个变量一个代表从当前行由左到当前位置有多少连续1
//另一个代表从上到当前位置有多少个连续的1
#include<bits/stdc++.h>
using namespace std;
struct myStruct{
    int row;//行连续
    int cow;//列连续
};
int main(){
    int N;
    int max=0;//最终的返回值
    cin>>N;
    int arr[N][N];
    myStruct dp[N][N];//预处理数组
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>arr[i][j];
            //填写dp数组
            dp[i][j].row=(arr[i][j]==0)?0:(j-1>=0?(dp[i][j-1].row+1):1);
            dp[i][j].cow=(arr[i][j]==0)?0:(i-1>=0?(dp[i-1][j].cow+1):1);
        }
    }
    //这样就预处理完了，根据预处理数组可以把判断一个点是否可以作为正方形的顶点的时间降至常数时间
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(arr[i][j]!=0){
                int row=dp[i][j].row;
                int cow=dp[i][j].cow;
                //取row和cow中较小的那一个作为正方形的边长
                int len=row<cow?row:cow;
                //找左下角顶点和右上角顶点
                while(len>0){
                                    if(j-len+1>=0){
                        if(dp[i][j-len+1].cow>=len){//如果向上连续的长度大于等于len继续
                            //找右上角顶点
                            if(i-len+1>=0){
                                    if(dp[i-len+1][j].row>=len){
                                        if(max<len){
                                            max=len;
                                            break;
                                        }
                                    }
                                
                            }
                        }
                }
                    len--;
                }

            }
        }
    }
//     for(int i=0;i<N;i++){
//         for(int j=0;j<N;j++)
//             cout<<dp[i][j].row<<" "<<dp[i][j].cow<<" ";
//         cout<<endl;
//     }
    cout<<max<<endl;
}