hdu 1505 City Game(hdu1506的二維推廣)

hdu 1505 City Game(hdu1506的二維推廣)

1.輸入的時候數據的時候要注意

2.1506的二維推廣

代碼：

#include
#include
#include
using namespace std;

const int INF=1<<30;
int a[1005][1005];
int L[1005];
int R[1005];

int main()
{
    int t;
    int m,n;
    int ans;
    char s[10];
    scanf("%d",&t);
    memset(a,0,sizeof(a));
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%s",s);
                if(s[0]=='F')
                    a[i][j]=1;
                else
                    a[i][j]=0;
            }
        }
        ans=-INF;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]==1)
                    a[i][j]+=a[i-1][j];
            }
            for(int j=1;j<=n;j++)
            {
                L[j]=j;
                while(L[j]>1&&a[i][L[j]-1]>=a[i][j])
                    L[j]=L[L[j]-1];
            }
            for(int j=n;j>=1;j--)
            {
                R[j]=j;
                while(R[j]=a[i][j])
                    R[j]=R[R[j]+1];
            }
            for(int j=1;j<=n;j++)
            {
                ans=max(ans,a[i][j]*(R[j]-L[j]+1));
            }
        }
        printf("%d\n",3*ans);
    }
    return 0;
}