HDU 2870 Largest Submatrix (单调栈)

http://acm.hdu.edu.cn/showproblem.php?

pid=2870

Largest Submatrix
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1569    Accepted Submission(s): 748

2 4
abcw
wxyz

3

矩阵中有7种字母:abcwxyz,w可替换为a或b,x可替换为b或c,y可替换为a或c,z可替换为a、b或c。求一个子矩阵，该矩阵中全部元素都同样，问该矩阵最大是多少？

分析：

首先将w,x,y,z换为a,b,c;得到3个01矩阵。然后就是求元素所有是1的最大子矩阵，能够转化为面积做。

维护出第i行各元素的“高度”，然后用单调栈向左/右找到比该点低的位置并记录，最后计算面积。

/*
 *
 * Author : fcbruce <fcbruce8964@gmail.com>
 *
 * Time : Sat 25 Oct 2014 07:10:43 PM CST
 *
 */
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld "%I64d"
#else
  #define lld "%lld"
#endif

#define maxm 
#define maxn 1007

using namespace std;

int trans[maxn][maxn][3];
char matrix[maxn][maxn];
int n,m;
int ql[maxn],qr[maxn],fl,rl,fr,rr;
int h[maxn];
int l[maxn],r[maxn];

inline void init(int x,int y,char ch)
{
  switch (ch)
  {
    case 'a':
      trans[x][y][0]=1;
      break;
    case 'b':
      trans[x][y][1]=1;
      break;
    case 'c':
      trans[x][y][2]=1;
      break;
    case 'w':
      trans[x][y][0]=trans[x][y][1]=1;
      break;
    case 'x':
      trans[x][y][1]=trans[x][y][2]=1;
      break;
    case 'y':
      trans[x][y][0]=trans[x][y][2]=1;
      break;
    case 'z':
      trans[x][y][0]=trans[x][y][1]=trans[x][y][2]=1;
      break;
  }
}

int solve(int k)
{
  int MAX=0;
  memset(h,0,sizeof h);
  for (int i=0;i<n;i++)
  {
    for (int j=0;j<m;j++)
    {
      if (trans[i][j][k]==1) h[j]++;
      else h[j]=0;
    }

    fl=fr=0;rl=rr=-1;
    for (int j=0;j<m;j++)
    {
      while (fl<=rl && h[ql[rl]]>=h[j]) rl--;
      if (fl<=rl) l[j]=ql[rl]+1;
      else l[j]=0;
      ql[++rl]=j;

      while (fr<=rr && h[qr[rr]]>=h[m-j-1]) rr--;
      if (fr<=rr) r[m-j-1]=qr[rr];
      else r[m-j-1]=m;
      qr[++rr]=m-j-1;
    }

    for (int j=0;j<m;j++)
      MAX=max(MAX,h[j]*(r[j]-l[j]));
  }

  return MAX;
}

int main()
{
#ifdef FCBRUCE
  freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE

  while (scanf("%d%d",&n,&m)==2)
  {
    for (int i=0;i<n;i++)
      scanf("%s",matrix[i]);

    memset(trans,0,sizeof trans);
    for (int i=0;i<n;i++)
      for (int j=0;j<m;j++)
        init(i,j,matrix[i][j]);

    int MAX=0;
    for (int i=0;i<3;i++)
      MAX=max(MAX,solve(i));

    printf("%d\n",MAX);
  }


  return 0;
}