uva 1330 - City Game 模拟

    扫描线，记录l,r,u,答案就是(r+l-1)*u

    实际上只要开个2维数组就可以了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define Maxn 1005
typedef int ma[Maxn][Maxn];
int w,h;
char org[Maxn][Maxn];
ma l,r,u;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&h,&w);
        int i,j;
        for(i=1;i<=h;i++)
            for(j=1;j<=w;j++)
            {
                org[i][j]=getchar();
                while(org[i][j]!='F'&&org[i][j]!='R')
                    org[i][j]=getchar();
            }
        int now=0,ans=0;
        for(i=0;i<=w;i++)l[0][i]=r[0][i]=1005;
        for(i=0;i<=w;i++)u[0][i]=0;
        for(i=1;i<=h;i++)
        {
            now=0;
            for(j=1;j<=w;j++)
            {
                if(org[i][j]=='R')
                {
                    l[i][j]=10000;u[i][j]=now=0;
                    continue;
                }
                now++;
                l[i][j]=min(l[i-1][j],now);
                u[i][j]=u[i-1][j]+1;
            }
            now=0;
            for(j=w;j>=1;j--)
            {
                if(org[i][j]=='R')
                {
                    r[i][j]=10005;now=0;
                    continue;
                }
                now++;
                r[i][j]=min(r[i-1][j],now);
                ans=max(ans,(l[i][j]+r[i][j]-1)*u[i][j]);
            }

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

半年以后重写：

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
char org[1005][1005];
int up[1005][1005],Left[1005][1005],Right[1005][1005],space;//space为当前位置行空格
#define INF 100000000
int main()
{
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        int i,j;
        for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
            scanf(" %c",&org[i][j]);
        for(j=0;j<=m;j++)
        {
            up[0][j]=0;
            Left[0][j]=Right[0][j]=INF;
        }
        for(i=1;i<=n;i++)
        {
            space=0;
            for(j=1;j<=m;j++)
            {
                if(org[i][j]=='R')
                {
                    up[i][j]=0;
                    Left[i][j]=Right[i][j]=INF;
                    space=0;
                    continue;
                }
                up[i][j]=up[i-1][j]+1;
                Left[i][j]=min(Left[i-1][j],space++);
            }
        }
        int ans=0;
        for(i=1;i<=n;i++)
            for(j=m,space=0;j>=1;j--)
            {
                if(org[i][j]=='R')
                {
                    space=0;
                    continue;
                }
                Right[i][j]=min(Right[i-1][j],space++); //获得右边边界，不含自己
                ans=max(ans,(Left[i][j]+Right[i][j]+1)*up[i][j]);
            }
        printf("%d\n",ans*3);
    }
}