自动搬运

查看原文

来自洛谷，原作者为

	BriMon 我曾经落败，如今依然

搬运于2025-08-24 21:27:52，当前版本为作者最后更新于2018-02-22 19:12:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

本蒟蒻来谈谈我的做法

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

最大正方形那道题，是设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;
}