Uva(1130)(City Game)

链接：https://vjudge.net/problem/UVA-1330
思路：首先先强调一下，这个题不要相信他题目的输入方式，可能每个字母间有很多空格，我就是这里被坑了很久，然后这个题的扫描发确实想不到，看了刘汝佳的题解才明白，然后自己写的，明显写复杂了，简单说一下吧，第一行先提出来单独处理，up表示从当前块往上最多有多少连续空位，left表示左边障碍物的最近位置，right同理，然后递推公式见书，因为我的面积是把所有right更新完后才做的，不像书上是边更新边算最大矩阵，所以我还要多一步判断，就是如果当前为空地，上面也为空地，那么左右最近距离就要拉上上面的最近距离一起取，否则只取本行的即可。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxx = 1010;
char a[maxx][maxx];
int t,n,m;
int up[maxx][maxx],left[maxx][maxx],right[maxx][maxx];

int main(){
    scanf("%d",&t);
    while(t--){
        char ch;
        scanf("%d%d",&n,&m);
        getchar();
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                scanf("%c",&ch);
            while(ch!='F'&&ch!='R')ch = getchar();//不要相信题目的输入方式
            a[i][j] = ch;
            }
        }

        int llmin = -1;//预处理第一行
        for(int i=0;i<m;i++){
            if(a[0][i]=='F'){
                up[0][i] = 1;
                left[0][i] = llmin;
            }
            else {
                up[0][i] = 0;
                left[0][i] = i;
                llmin = i;
        }
    }
        llmin = m;
        for(int i=m-1;i>=0;i--){
        if(a[0][i]=='F'){
                right[0][i] = llmin;
            }
            else {
                right[0][i] = i;
                llmin = i;
        }
        }

        for(int i=1;i<n;i++){
            int lmin = -1;
            int rmin = m;
            for(int j=0;j<m;j++){
                if(a[i][j]=='F'){
                    up[i][j] = up[i-1][j]+1;
                    if(a[i-1][j]=='R')//分情况讨论
                        left[i][j] = lmin;
                    else
                    left[i][j] = max(left[i-1][j],lmin);
            }

            else{
                up[i][j] = 0;
                left[i][j] = j;
                lmin = j;
            }
            }
            for(int j=m-1;j>=0;j--){
                if(a[i][j]=='F'){
                    if(a[i-1][j]=='R')
                        right[i][j] = rmin;
                        else
                    right[i][j] = min(rmin,right[i-1][j]);
                }
                else{
                    right[i][j] = j;
                    rmin = j;
                }
            }
        }

        int maxres = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
            maxres = max(maxres,(right[i][j]-left[i][j]-1)*up[i][j]);
            }
        }
        printf("%d\n",maxres*3);
    }
    return 0;
}