2014
02-17

# Largest Submatrix

Now here is a matrix with letter ‘a’,'b’,'c’,'w’,'x’,'y’,'z’ and you can change ‘w’ to ‘a’ or ‘b’, change ‘x’ to ‘b’ or ‘c’, change ‘y’ to ‘a’ or ‘c’, and change ‘z’ to ‘a’, ‘b’ or ‘c’. After you changed it, what’s the largest submatrix with the same letters you can make?

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.

2 4
abcw
wxyz

3

/*

一道简单的dp。
是hdu1505的小拓展、hdu1505又是hdu1506的小拓展- -，这个题

2013-04-09
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1005;

int n,m,ans;
char map[N][N],map_t[N][N];
int cnt[N][N],le[N],ri[N];

void solve(char cc,char a,char b,char c)
{
int i,l,temp;

for(i=1;i<=n;i++)
for(l=1;l<=m;l++)
{
if(map[i][l]==a || map[i][l]==b || map[i][l]==c)
map_t[i][l]=cc;
else	map_t[i][l]=map[i][l];
}

memset(cnt[0],0,sizeof(cnt[0]));
memset(map_t[0],0,sizeof(map_t[0]));
for(i=1;i<=n;i++)
{
cnt[i][0]=cnt[i][m+1]=-1;
for(l=1;l<=m;l++)
{
le[l]=ri[l]=l;
if(map_t[i][l]!=cc)	cnt[i][l]=0;
else	cnt[i][l]=cnt[i-1][l]+1;
}
for(l=2;l<=m;l++)
{
if(!cnt[i][l])	continue;
while(cnt[i][le[l]-1]>=cnt[i][l])	le[l]=le[le[l]-1];
}
for(l=m-1;l>0;l--)
{
if(!cnt[i][l])	continue;
while(cnt[i][ri[l]+1]>=cnt[i][l])	ri[l]=ri[ri[l]+1];
}
for(l=1;l<=m;l++)
{
if(!cnt[i][l])	continue;
temp=cnt[i][l]*(ri[l]-le[l]+1);
if(ans<temp)	ans=temp;
}
}
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)!=-1)
{
for(i=1;i<=n;i++)	scanf("%s",map[i]+1);
ans=0;
solve('a','w','y','z');
solve('b','w','x','z');
solve('c','x','y','z');
cout<<ans<<endl;
}
return 0;
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法