1964.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#define debug 0
#define NMAX 1003
int h[NMAX][NMAX];
int l[NMAX],r[NMAX];
int i,j,t,k,T,M,N;


main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
    char ch;
    int p,q,k;
    long max,s;
    scanf("%d",&T);
    for(t=0;t<T;t++)
    {
        scanf("%d%d",&M,&N);
        max=0;
        for(i=0;i<M;i++)
        {
            for(j=0;j<N;j++)
            {
                do
                {
                    scanf("%c",&ch);
                }while(ch!='F'&&ch!='R');
                if(ch=='F')
                {
                    h[i][j]=1;
                }
                else
                {
                    h[i][j]=0;
                }
            }
        }

        for(i=1;i<M;i++)
        {
            for(j=0;j<N;j++)
            {
                if(h[i][j])
                {
                    h[i][j]+=h[i-1][j];
                    
                }
//               printf("h%d,%d=%d ",i,j,h[i][j]);
            }
 //                     printf("\n");
        }
        
        for(i=0;i<M;i++)
        {



            if(h[i][0])
            {
                l[0]=0;
            }
            else
            {
                l[0]=-1;
            }
            for(j=1;j<N;j++)
            {
                if(h[i][j])
                {

                    k=j;
                    l[j]=j;
                    while(h[i][j]<=h[i][k-1]&&k!=0)
                    {
                        k=l[k-1];
                    }
                    l[j]=k;
                }
                else
                {
                    l[j]=-1;
                }
            }
                        
                    
                    
                    
                    
                    
               
            if(h[i][N-1])
                r[N-1]=N-1;
            else
                r[N-1]=-1;
            for(j=N-2;j>=0;j--)
            {
                if(h[i][j])
                {

                    k=j;
                    r[j]=j;
                    while(h[i][j]<=h[i][k+1]&&k!=N-1)
                    {
                        k=r[k+1];
                    }
                    r[j]=k;
                }
                else
                {
                    r[j]=-1;
                }
            }
            for(j=0;j<N;j++)
            {
                if(h[i][j])
                {
                    s=h[i][j]*(r[j]-l[j]+1);
                    if(max<s)
                    {
                        max=s;
                    }
                }
//                printf("s%d,%d=%d ",i,j,s);
                
            }
//            printf("\n");
            
        }
        printf("%ld\n",max*3);
    }
        
                


    




#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}