uva1330 City Game

题目链接。

分析：

《训练指南》上的代码是二维的，优化了下，改成了一维的。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const int maxn = 1000 + 10;

int _left[maxn], _right[maxn], _up[maxn];
char mat[maxn];

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

            int lo = -1, ro = n;
            for(int j=0; j<n; j++){
                if(mat[j] == 'R') { _up[j] = _left[j] = 0; lo = j; }
                else{
                    _up[j] = (i == 0 ? 1 : _up[j]+1);
                    _left[j] = (i == 0 ? lo+1 : max(_left[j], lo+1));
                }
            }

            for(int j=n-1; j>=0; j--){
                if(mat[j] == 'R') { _right[j] = n; ro = j; }
                else{
                    _right[j] = (i == 0 ? ro-1 : min(_right[j], ro-1));
                    ans = max(ans, _up[j]*(_right[j]-_left[j]+1));
                }
            }
        }
        printf("%d\n", ans*3);
    }


    return 0;
}