邱老师降临小行星

Time Limit: 20 Sec  Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

Input

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

char s[][];

int dp[][][];

int dx[]={-,,,,,,,-};

int dy[]={,,,,,-,-,};

int n,m;

void dfs(int i,int j,int k)

{

    if(k%==)

    {

        if(i+dx[k]<||i+dx[k]>=n||j+dy[k]<||j+dy[k]>=m)

            dp[i][j][k]=;

        else if(s[i+dx[k]][j+dy[k]]=='')

            dp[i][j][k]=;

        else

        {

            if(dp[i+dx[k]][j+dy[k]][k+]==-)

                dfs(i+dx[k],j+dy[k],k+);

            dp[i][j][k]=;

            dp[i][j][k]+=dp[i+dx[k]][j+dy[k]][k+];

        }

    }

    else

    {

        if(i+dx[k]<||i+dx[k]>=n||j+dy[k]<||j+dy[k]>=m)

            dp[i][j][k]=;

        else if(s[i+dx[k]][j+dy[k]]=='')

            dp[i][j][k]=;

        else

        {

            if(dp[i+dx[k]][j+dy[k]][k-]==-)

                dfs(i+dx[k],j+dy[k],k-);

            dp[i][j][k]=;

            dp[i][j][k]+=dp[i+dx[k]][j+dy[k]][k-];

        }

    }

}

int main()

{

    int t=read();

    for(int cas=;cas<=t;cas++)

    {

        n=read(),m=read();

        for(int i=;i<n;i++)

            for(int j=;j<m;j++)

                for(int k=;k<;k++)

                    dp[i][j][k]=-;

        for(int i=;i<n;i++)

            scanf("%s",s[i]);

        int ans2=;

        for(int i=;i<n;i++)

        {

            for(int j=;j<m;j++)

            {

                if(s[i][j]=='')

                    continue;

                int ans=;

                if(dp[i][j][]==-)

                    dfs(i,j,);

                ans+=dp[i][j][];

                if(dp[i][j][]==-)

                    dfs(i,j,);

                ans+=dp[i][j][];

                if(dp[i][j][]==-)

                    dfs(i,j,);

                ans+=dp[i][j][];

                if(dp[i][j][]==-)

                    dfs(i,j,);

                ans+=dp[i][j][];

                ans2=max(ans2,ans);

            }

        }

        printf("%d\n",ans2);

    }

}