题解 P1387 【最大正方形】

· · 题解

题解 P1387 【最大正方形】

感觉我的代码是比较短的辣QWQ

动态规划，状转方程：

if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;

说明：

f[i][j]表示以节点i,j为右下角，可构成的最大正方形的边长。

只有a[i][j]==1时，节点i,j才能作为正方形的右下角；

对于一个已经确定的f[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；

对于一个待确定的f[i][j]，我们已知f[i-1][j]，f[i][j-1]，f[i-1][j-1]的值，如下：

f数组:

? ? ? ?

? ? 2 1

? ? 3 ?

? ? ? ?

则说明原a数组：

1 1 1 0

1 1 1 1

1 1 1 1

? ? ? ?

由此得出状态转移方程：

if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;

for example:

a[i][j]:

0 0 0 1

1 1 1 1

0 1 1 1

1 1 1 1

f[i][j]:

0 0 0 1

1 1 1 1

0 1 2 2

1 1 2 3

#include <iostream>
#include <cstdio>
using namespace std;
int a[101][101],n,m,f[101][101],ans;
int main()
{
    scanf("%d%d",&n,&m);//读入
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            //因为只需用到i，j上方，左方，左上方的信息，读入同步处理
            if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
            ans=max(ans,f[i][j]);//同步更新答案
        }
    printf("%d",ans);
}
ans=3