HDU 1505 & POJ 1964 City Game (遞推+掃描法)

題意：一個矩陣，有些格子是F，有些是R，要你找到最大的子矩陣使得矩陣內全是F

思路:直接枚舉每個子矩陣，顯然復雜度是O(m^3 n^3)，顯然TLE。

我們可以使用掃描法：用up(i,j)表示格子(i,j)懸垂線(懸垂線就是指這個格子往上走遇到第一個R的格子之前的線段)的長度。left(i,j)表示懸垂線往左掃最左能移動到的位置(遇到R會停止)，right(i,j)表示懸垂線往右掃最右能移動到的位置(遇到R會停止)。那麼格子(i,j)可以對應一個這樣的最大F矩形：以第i行作為底邊，第i-up(i,j)+1行作為上底邊，left(i,j)所在列為左邊，right(i,j)所在列作為右邊的矩形。

那麼最終答案就是每個格子對應的矩形中的最大值。

up(i,j)可以用遞推式：（1）若map[i][j]=='F'，up(i,j)=up(i-1,j)+1 （2）若map[i][j]=='R'，up(i,j)=0

left(i,j)可以用遞推式：（1）若map[i][j]=='F'，left(i,j)=max{left(i-1,j),lo+1}  (lo是格子(i,j)左邊最近的'R'的列)（2）若map[i][j]=='R'，left(i,j)=0

right(i,j)可以用遞推式：（1）若map[i][j]=='F'，right(i,j)=max{right(i-1,j),ro-1} (ro是格子(i,j)右邊最近的'R'的列)（2）若map[i][j]=='R'，right(i,j)=n

注意：這個題目讀入數據規模較大，用scanf會TLE。。。。getchar()才行。。。

#include<cstdio>
#include<iostream>
#define MAXN 1005
using namespace std;
int T,n,m,righ[MAXN][MAXN],up[MAXN][MAXN],lef[MAXN][MAXN];
char map[MAXN][MAXN];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int ans=0;
        scanf("%d%d",&m,&n); getchar();
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
            {
                char ch=getchar();
                while(ch!='F' && ch!='R') ch=getchar();//處理讀入，注意用while，直到讀入為F或者R為止
                map[i][j]=ch;
            }
        for(int j=0;j<n;++j)
        for(int i=0;i<m;++i)
            if(map[i][j]=='R') up[i][j]=0;
            else up[i][j]=i? up[i-1][j]+1:1;//遞推up(i,j)

        for(int i=0;i<m;++i)
        for(int j=0,lo=-1;j<n;++j)
            if(map[i][j]=='R') lo=j,lef[i][j]=0;
            else lef[i][j]=i? max(lo+1,lef[i-1][j]):lo+1;//遞推left(i,j)

        for(int i=0;i<m;++i)
        for(int j=n-1,ro=n;j>=0;--j)
            if(map[i][j]=='R') ro=j,righ[i][j]=n;
            else righ[i][j]=i? min(ro-1,righ[i-1][j]):ro-1;//遞推right(i,j)

        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(map[i][j]=='F') ans=max(ans,(righ[i][j]-lef[i][j]+1)*up[i][j]);//計算答案取最大值

        printf("%d\n",ans*3);
    }
    return 0;
}