AcWing 1612. 最大正方形

题目

在一个由 和 组成的 的二维矩阵内，找到只包含 的最大正方形，并返回其面积。

输入格式

第一行包含两个整数 ，表示二维矩阵大小。

接下来 行，每行包含 个整数，每个整数只可能是 或 。

输出格式

输出只包含 的最大正方形的面积。

数据范围

输入样例：

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出样例：

4

题解

#include <iostream>
#include <algorithm>
#define N 1010

using namespace std;

// 集合：所有右下角以i,j结尾的正方形的集合
// 属性：最大边长
// 状态转移： 左边三格子的边长取最小值 + 1
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
        {
            scanf("%d", &f[i][j]);
            if (f[i][j])
            {
                f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j -1])) + 1;
                ans = max(ans, f[i][j]);
            }
        }

    cout << ans * ans << endl;

    return 0;
}