單調棧和簡單DP
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point{
int h;
int w;
}stack[1005];
int n,m;
char in[1010];
int map[1010][1010];
int dp[1010][1010];
int sum[1010][1010];
int DP1(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
dp[i][j]=1;
if(map[i][j]==map[i-1][j-1] && map[i][j]!=map[i-1][j] && map[i][j]!=map[i][j-1])
dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
}
int ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
ans=max(dp[i][j]*4,ans);
return ans;
}
int sea(int *sum){
int i;
int lasth=0,top=0,ans=0;
for(i=1;i<=m;i++){
if(sum[i]>=lasth){
stack[top].h=sum[i];
stack[top++].w=1;
}
else{
int totw=0;
while(top>0){
if(stack[top-1].h>sum[i]){
if((totw+stack[top-1].w+stack[top-1].h)*2>ans)
ans=(totw+stack[top-1].w+stack[top-1].h)*2;
totw+=stack[top-1].w;
top--;
}
else
break;
}
stack[top].h=sum[i];
stack[top++].w=totw+1;
}
lasth=stack[top-1].h;
}
int totw=0;
while(top>0){
if(stack[top-1].h==0)
break;
if((totw+stack[top-1].w+stack[top-1].h)*2>ans)
ans=(totw+stack[top-1].w+stack[top-1].h)*2;
totw+=stack[top-1].w;
top--;
}
return ans;
}
int DP2(int s){
int i,j,ans=0;
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if(map[i][j]==s)
sum[i][j]=sum[i-1][j]+1;
else
sum[i][j]=0;
ans=max(ans,sea(sum[i]));
}
return ans;
}
int main(){
int i,j,t,T;
scanf("%d",&T);
for(t=1;t<=T;t++){
memset(map,0,sizeof(map));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%s",&in[1]);
for(j=1;j<=m;j++)
map[i][j]=(in[j]=='B');
}
int ans=DP1();
ans=max(ans,DP2(0));
ans=max(ans,DP2(1));
printf("Case #%d: ",t);
printf("%d\n",ans);
}
return 0;
}
