动态规划

定义$f[i][j]$表示以$(i,j)$坐标为右下角的正方形的边长

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;


void getS(int R, int C, const vector<vector<int>>&M){
    int f[R][C];
    memset(f, 0x00, sizeof f);
    int maxL = 0;
    for(int i=0; i<R; ++i){
        for(int j=0; j<C; ++j){
            if(i==0) f[i][j] = M[i][j];
            if(j==0) f[i][j] = M[i][j];
            if(i>0 && j>0 && M[i][j]==1)
                f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1]))+1;
            maxL = max(maxL, f[i][j]);
        }
    }
    cout<<maxL*maxL<<endl;
}

int main(){

    int R, C;
    vector<vector<int>> M;
    cin>>R>>C;
    M = vector<vector<int>>(R, vector<int>(C, 0));
    for(int i=0; i<R; ++i){
        for(int j=0; j<C; ++j){
            cin>>M[i][j];
        }
    }

    getS(R, C, M);
    return 0;
}