Acwing 1612. 最大正方形

Acwing 1612. 最大正方形

思路：

Dp，f[i][j]表示以（i，j）为右下角的正方形中，最大的边长。

而每个点的边长更新至于上面左边，以及左上角有关，所以更新等式为：
f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;

代码：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e3+5;

int g[N][N];
int f[N][N];
int n, m;

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
        }
    }
    int len = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j]){
                f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                len = max(len, f[i][j]);
            }
        }
    }
    cout << len * len;
    return 0;
}