题解 P1681 【最大正方形II】

· · 题解

惊！ 在题解里竟然没有我的做法（汗-_-||

本蒟蒻来谈谈我的做法

这道题就是最大正方形的变式；

最大正方形那道题，是设dp[i][j]为在(i,j)以上的最大正方形；

本题就是多加了一个条件，满足黑白相间的最大正方形；

所以可以多设一维表示此位置是1还是0；

就有了dp[i][j][0/1] 表示在(i, j)以上， 且本位是0/1的最大符合条件的正方形；

转移方程：

如果本位是1: f[i][j][1] = min(f[i-1][j][0], min(f[i][j-1][0], f[i-1][j-1][1])) + 1

如果是0: f[i][j][0] = min(f[i-1][j][1], min(f[i][j-1][1], f[i-1][j-1][0])) + 1

然后每步后取max就行了；

代码： 

#include <bits/stdc++.h>
using namespace std;

int f[1501][1501][2];
int n, m, a[1505][1505];
int ans = -1;
inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

int main()
{
    n = read(), m = read();
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            a[i][j] = read();
        }
    }
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            if(a[i][j] == 1) f[i][j][1] = min(f[i-1][j][0], min(f[i][j-1][0], f[i-1][j-1][1])) + 1, ans = max(ans, f[i][j][1]);
            if(a[i][j] == 0) f[i][j][0] = min(f[i-1][j][1], min(f[i][j-1][1], f[i-1][j-1][0])) + 1, ans = max(ans, f[i][j][0]);
        }
    }

    printf("%d",ans);
    return 0;
}