P1681 最大正方形II (动态规划)

题目背景

忙完了学校的事，v神终于可以做他的“正事”：陪女朋友散步。一天，他和女朋友走着走着，不知不觉就来到了一个千里无烟的地方。v神正要往回走，如发现了一块牌子，牌子上有有一行小字和一张图，小字说道：“找到图上最大的交错正方形之后和我联系，这块地就是你的了。”在房价疯长的年代，v神当然不愿错过这个机会，于是开始找了起来……以v神的能力当然找不出来了，你能帮v神找出来吗？

题目描述

图上有一个矩阵，由N*M个格子组成，这些格子由两种颜色构成，黑色和白色。请找到面积最大的且内部是黑白交错（即两个相连的正方形颜色不能相同）的正方形。

输入输出格式

输入格式：

第一行两个整数N和M，分别表示行数和列数。接下来有N行，每行M个数，0或1分别表示这个格子是黑色或白色。

输出格式：

仅有一行，表示满足条件最大正方形的边长

输入输出样例

输入样例#1：

3 3

0 1 0

1 0 0

1 1 1

输出样例#1：

说明

样例解释：

(1,1)到(2,2)这个正方形是满足条件的，它的边长是2

数据范围约定：

对于30%的数据，N <= 20

对于60%的数据，N <=300

对于100%的数据，N <= 1500

Solution

这个题和之前的一道题很相似啊...

不过就是有一点点不同.就是原来的单纯是一样的矩形即可.

但这里是 01 矩形.

所以需要一点变化,也就是将形如 c[i][j] 而且满足 i+j %2==1的,我们将其取反即可转化成和原来一样的形状...

对于这个,自己画个图就可以理解应该.

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1508;

int n,m,ans;

int c[maxn][maxn];

int f[maxn][maxn];

int main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

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

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

    {

    	cin>>c[i][j];

        if ((i+j)&1)

        c[i][j]=1-c[i][j];

    }

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

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

    {

       if(!c[i][j])

       {

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

          ans=max(ans,f[i][j]);

       }

    }

    memset(f,0,sizeof(f));

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

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

    {

       if(c[i][j])

       {

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

          ans=max(ans,f[i][j]);

       }

    }

    //要做两遍,想一想为什么?

    cout<<ans<<endl;

    return 0;

}

巴特西