hud4328 - Cut the cake(垂線法)

Cut the cake

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1175    Accepted Submission(s): 441

Problem Description Mark bought a huge cake, because his friend ray_sun’s birthday is coming. Mark is worried about how to divide the cake since it’s so huge and ray_sun is so strange. Ray_sun is a nut, you can never imagine how strange he was, is, and going to be. He does not eat rice, moves like a cat, sleeps during work and plays games when the rest of the world are sleeping……It is not a surprise when he has some special requirements for the cake. A considering guy as Mark is, he will never let ray_sun down. However, he does have trouble fulfilling ray_sun’s wish this time; could you please give him a hand by solving the following problem for him?

  The cake can be divided into n*m blocks. Each block is colored either in blue or red. Ray_sun will only eat a piece (consisting of several blocks) with special shape and color. First, the shape of the piece should be a rectangle. Second, the color of blocks in the piece should be the same or red-and-blue crisscross. The so called ‘red-and-blue crisscross’ is demonstrated in the following picture. Could you please help Mark to find out the piece with maximum perimeter that satisfies ray_sun’s requirements?

Input The first line contains a single integer T (T <= 20), the number of test cases.

  For each case, there are two given integers, n, m, (1 <= n, m <= 1000) denoting the dimension of the cake. Following the two integers, there is a n*m matrix where character B stands for blue, R red.

Output For each test case, output the cased number in a format stated below, followed by the maximum perimeter you can find.  

Sample Input

2
1 1
B
3 3
BBR
RBB
BBB
        

Sample Output

Case #1: 4
Case #2: 8
        

Author BJTU  

Source 2012 Multi-University Training Contest 3  

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN=2147483647;
int n,m,ans,ans1,ans2,T,a[1001][1001],Right[1001][1001],Left[1001][1001],up[1001][1001];
int Find(int x)
{
    for(int i=1;i <= m;i++)
    {
        Left[0][i]=-1;
        Right[0][i]=m+1;
    }
    for(int i=1;i <= n;i++)
     for(int j=1;j <= m;j++)
      up[i][j]=a[i][j] == x ? up[i-1][j]+1 : 0;
    for(int i=1;i <= n;i++)
    {
        int now=0;
        for(int j=1;j <= m;j++)
         if(a[i][j] != x)
         {
             now=j;
             Left[i][j]=-1;
         }
         else Left[i][j]=max(now+1,Left[i-1][j]);
    }    
    for(int i=1;i <= n;i++)
    {
        int now=m+1;
        for(int j=m;j >= 1;j--)
         if(a[i][j] != x)
         {
             now=j;
             Right[i][j]=m+1;
         }
         else Right[i][j]=min(now-1,Right[i-1][j]);
    }
    int v=0;
    for(int i=1;i <= n;i++)
     for(int j=1;j <= m;j++)
      if(a[i][j] == x) v=max(v,(up[i][j]+Right[i][j]-Left[i][j]+1));
    return 2*v;
} 
void Flip()
{
    for(int i=1;i <= n;i++)
     for(int j=1;j <= m;j++)
      if((i+j)%2 == 0) a[i][j]*=-1; 
}
int main()
{
    cin.sync_with_stdio(false); 
    cin>>T;
    for(int t=1;t <= T;t++)
    {
        cin>>n>>m;
        for(int i=1;i <= n;i++)
         for(int j=1;j <= m;j++)
            {
                char c;
            cin>>c;
            a[i][j]=c == 'B' ? 1:-1;    
         }
        ans1=max(Find(1),Find(-1));
        Flip();
        ans2=max(Find(1),Find(-1));
        cout<<"Case #"<<t<<": "<<max(ans1,ans2)<<endl; 
    }
 }