• <input id="auww4"></input>
  • <input id="auww4"><acronym id="auww4"></acronym></input>
  • <input id="auww4"><u id="auww4"></u></input>
    <object id="auww4"><acronym id="auww4"></acronym></object>
    <menu id="auww4"></menu><input id="auww4"><u id="auww4"></u></input>
    <input id="auww4"><u id="auww4"></u></input>
  • F.A.Q
    Hand In Hand
    Online Acmers
    Forum | Discuss
    Statistical Charts
    Problem Archive
    Realtime Judge Status
    Authors Ranklist
     
         C/C++/Java Exams     
    ACM Steps
    Go to Job
    Contest LiveCast
    ICPC@China
    Best Coder beta
    VIP | STD Contests
    Virtual Contests
        DIY | Web-DIY beta
    Recent Contests
    Author ID 
    Password 
     Register new ID

    O(n2)的算法,計算up,left,right值。。

    Posted by yomin at 2013-07-03 08:27:16 on Problem 1505
    (19)  


    #include <iostream>
    #include<stdio.h>
    #include<string.h>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<set>
    #define leps 1e-6
    using namespace std;
    const int maxn=1000+10;
    const int maxc=1e6+7;
    long long sum[maxn];
    int n,m,temp,t;
    int map[maxn][maxn];
    int up[maxn][maxn],_left[maxn][maxn],_right[maxn][maxn];
    /*
    void print(int a[][maxn])
    {
        for(int i=1;i<=n;i++)
        {
             for(int j=1;j<=m;j++)
             cout<<a[i][j]<<" ";
             cout<<endl;
        }
        cout<<endl;
    }
    */
    int main()
    {
        char ch;
        freopen("in","r",stdin);
        scanf("%d",&t);
        while(t--)
        {
            memset(up,0,sizeof(up));
            memset(_left,0,sizeof(_left));
            memset(_right,0,sizeof(_right));
            memset(map,0,sizeof(map));
            scanf("%d %d",&n,&m);
    
            for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>ch;
                if(ch=='R')map[i][j]=0;
                else map[i][j]=1;
            }
            //print(map);
    
            for(int j=1;j<=m;j++)
            {
                if(map[1][j]==0)up[1][j]=0;
                else up[1][j]=1;
            }
            for(int i=2;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(map[i][j]==0)up[i][j]=0;
                    else up[i][j]=up[i-1][j]+1;
                }
            }
            //print(up);
    
            int lo=0;
            for(int j=1;j<=m;j++)
            {
                if(map[1][j]==0)
                {
                    _left[1][j]=0;
                    lo=j;
                }
                else _left[1][j]=lo+1;
            }
            for(int i=2;i<=n;i++)
            {
                lo=0;
                for(int j=1;j<=m;j++)
                {
                    if(map[i][j]==0)
                    {
                       _left[i][j]=0;
                       lo=j;
                    }
                    else _left[i][j]=max(_left[i-1][j],lo+1);
                }
            }
            //print(_left);
    
    
            lo=m+1;
            for(int j=m;j>=1;j--)
            {
                if(map[1][j]==0)
                {
                    _right[1][j]=m+1;
                    lo=j;
                }
                else _right[1][j]=lo-1;
            }
            for(int i=2;i<=n;i++)
            {
                lo=m+1;
                for(int j=m;j>=1;j--)
                {
                    if(map[i][j]==0)
                    {
                        _right[i][j]=m+1;
                        lo=j;
                    }
                    else _right[i][j]=min(_right[i-1][j],lo-1);
                }
            }
            //print(_right);
    
            int ans=0;
            for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            ans=max(ans,up[i][j]*(_right[i][j]-_left[i][j]+1));
            printf("%d\n",3*ans);
        }
        return 0;
    }

    Followed by:


    Post your reply here:

    Author ID
    Password
    Title
    Content  
     
    Hangzhou Dianzi University Online Judge 3.0
    Copyright © 2005-2020 HDU ACM Team. All Rights Reserved.
    Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
    Total 0.000000(s) query 5, Server time : 2020-11-09 02:28:26, Gzip enabled
    棋牌