【题解】LA 3029【City Game】

分析

暴力显然不可行,这里考虑扫描线。
将每个格子向上延伸的空格看成一条悬线,并用$up(i,j),left(i,j),rigth(i,j)$表示格子$(i,j)$的悬线长度以及该悬线向左或向右运动的最远列号。
如图24:

这样每个格子$(i,j)$对应一个以第$i$行为下边界,高度为$up(i,j)$,左右边界分别为$left(i,j),right(i,j)$的矩形,显然这些矩形面积最大的就是答案所求。
当第$i$行第$j$列不是空格时,三个数组的值为零,否则$up(i,j)=up(i – 1,j)+1$,显然$left(i,j)=\max(left(i-1,j),lo+1))$ $right(i,j)=min(right(i-1,j),ro-1)$,$lo,ro$分别为第$i$行第$j$列左边最近障碍格的列编号和右边最近的障碍格的列编号。

代码

#include<cstdio>
#include<algorithm>
using std::max;using std::min;
const int MAXN = 1000 + 6;
int mat[MAXN][MAXN],up[MAXN][MAXN],left[MAXN][MAXN],right[MAXN][MAXN];

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int m,n;scanf("%d %d",&m,&n);
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int c = getchar();
                while(c != 'F' && c != 'R') c = getchar();
                mat[i][j] = c == 'F' ? 0 : 1;
            }
        }

        int ans = 0;
        for(int i = 0;i < m;i++){
            int lo = -1,ro = n;
            for(int j = 0;j < n;j++){
                if(mat[i][j] == 1) up[i][j] = left[i][j] = 0,lo = j;
                else up[i][j] = i == 0 ? 1 : up[i - 1][j] + 1,left[i][j] = i == 0 ? lo + 1 : max(left[i - 1][j],lo + 1);
            }
            for(int j = n - 1;j >= 0;j--){
                if(mat[i][j] == 1) right[i][j] = n,ro = j;
                else right[i][j] = i == 0 ? ro - 1 : min(right[i - 1][j],ro - 1),ans = max(ans,up[i][j] * (right[i][j] - left[i][j] + 1));
            }
        }
        printf("%d\n",ans * 3);
    }

    return 0;
}