HihoCoder1664 01间隔方阵（[Offer收割]编程练习赛40）（DP）

给定一个NxM的01矩阵，小Hi希望从中找到一个01间隔的子方阵，并且方阵的边长越大越好。

例如对于

0100100

1000101

0101010

1010101

0101010

在右下角有一个4x4的01间隔方阵。

Input

第一行包含两个整数N和M。

以下N行M列包含一个NxM的01矩阵。

对于30%的数据，1 ≤ N, M ≤ 250

对于100%的数据，1 ≤ N, M ≤ 1000

Output

输出最大的01间隔方阵的边长。

Sample Input

5 7

0100100

1000101

0101010

1010101

0101010

Sample Output

4

面积DP。

加强版：hihocoder1673

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

const int maxn=;

char c[maxn][maxn];

int L[maxn][maxn],H[maxn][maxn];

int a[maxn][maxn];

int main()

{

    int n,m,i,j,ans=;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++) scanf("%s",c[i]+);

    for(i=;i<=n;i++) L[i][]=;

    for(i=;i<=m;i++) H[][i]=;

    for(i=;i<=n;i++)

      for(j=;j<=m;j++)

        L[i][j]=c[i][j]==c[i][j-]?:L[i][j-]+;          //左延伸

    for(i=;i<=m;i++)

      for(j=;j<=n;j++)

        H[j][i]=c[j][i]==c[j-][i]?:H[j-][i]+;          //上延伸

    for(i=;i<=n;i++)

     for(j=;j<=m;j++){

         if(i==||j==||c[i][j]!=c[i-][j-])a[i][j]=;   //对角线是一样的

         else {

            a[i][j]=min(a[i-][j-]+,L[i][j]);

            a[i][j]=min(a[i][j],H[i][j]);

         }

         if(a[i][j]>ans) ans=a[i][j];//这一行复制过来的时候被删了。。。

     }

    printf("%d\n",ans);

    return ;

}