题目描述

涛涛的画是一个 n * m 的矩形，我们用 B 来表示黑色，W 来表示白色。涛涛每次可以让一整行行的颜色取反，就是说黑色的变成白色，白色的变成黑色。且该操作可以重复任意多次。 现在，请你告诉他，在进行任意多次行取反操作后，最大的正方形色块的大小是多少（色块是指一块连续的颜色相同的区域）。 注意，该正方形的边界必须与画纸平行。

输入格式

第一行两个整数 n 和 m 接下来 n 行，每行一个长度为 m 的字符串，表示涛涛的画

输出格式

一行一个整数，表示最大正方形的大小

样例

• Input 1

``

Input 1

2 2 
WW
WW

Output 1

4

Input 2

5 5
WWWWW
WBBBW
WBBBW
WBBBW
WWWWW

Output 2

9

Input 3

5 5
WWBWW
WBBBW
BBBBB
WBBBW
WWBWW

Output 3

9

样例解释 样例一 显然的，存在一个 2 * 2 的色块

样例二 可以发现，无论怎样的按照行取反颜色 只能存在一个 3 * 3 的色块 （其实可以存在一个 3 * 5 的色块，但是我们只问了正方形的色块）

数据范围 对于 30% 的数据，n，m ≤ 50 对于 60% 的数据，n，m ≤ 400 对于 100% 的数据，n，m ≤ 3000

#include<bits/stdc++.h>
using namespace std;
int a[3010][3010];
char s[3010][3010];
int lst[3010][3010];
int sum1[3010][3010];
int dp[3010][3010];
int n,m;
void Init(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sum1[i][j]=sum1[i][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=2;j<=m;j++){
			lst[i][j]=lst[i-1][j]+(!(a[i][j]==a[i][j-1]));
		}
	}
	for(int i=1;i<=n;i++){
		dp[1][i]=dp[i][1]=1;
	}
	return;
}
int main(){
	//freopen("art4.in","r",stdin);
	//freopen("art.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++){
			a[i][j]=(s[i][j]=='B'?1:2);
			//cout<<a[i][j]<<" ";
		}
		//cout<<endl;
	}
	//cout<<endl;
	Init(); 
	int mx=1;
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			/*###B*/
			/*###B*/
			/*###B*/
			/*WWWW*/
			dp[i][j]=1;
			int id=dp[i-1][j-1];//第 i-1 行到第 i-1-id+1 行 
			int ans1=lst[i-1][j]-lst[i-1-id][j];
			//cout<<ans1<<" ";
			int ans2=sum1[i][j]-sum1[i][j-1-id];
			if(!ans1 && (ans2==(id+1) || ans2==(id+1)*2)){
				dp[i][j]=dp[i-1][j-1]+1;
			}
			mx=max(mx,dp[i][j]);
			//printf("%d ",dp[i][j]);
		}
		//cout<<endl;
	}
	long long ret=(1ll*mx)*(1ll*mx);
	printf("%lld\n",ret);
	return 0;
} 

复杂度正确，但是写挂了，求调2关