#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
int map[102][102];
int n,m;
int vi[102][102][4];
int d[4][2]={-1,0,1,0,  0,-1,  0,  1};
int dp[102][102];
int   dfs(int x,int y)
{
    if(dp[x][y]!=-1) return dp[x][y];
    int x0,y0;
    int tmp=0;
    for(int i=0;i<4;i++)
    {
        if(vi[x][y][i])
        {
            x0=x+d[i][0];
            y0=y+d[i][1];
            tmp=dfs(x0,y0)+1;
            dp[x][y]=max(dp[x][y],tmp);
        }
    }
    if(dp[x][y]==-1) dp[x][y]=1;
    return dp[x][y];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(vi,0,sizeof(vi));
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&map[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(i!=1&&map[i][j]>map[i-1][j]) vi[i][j][0]=1;
                if(i!=n&&map[i][j]>map[i+1][j]) vi[i][j][1]=1;
                if(j!=1&&map[i][j]>map[i][j-1]) vi[i][j][2]=1;
                if(j!=m&&map[i][j]>map[i][j+1]) vi[i][j][3]=1;
            }
        int ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(dp[i][j]=-1)
                   dfs(i,j);
                ans=max(ans,dp[i][j]);
            }

        printf("%d\n",ans);
    }
    return 0;
}

• Re:记忆化搜索 (1259) hzoi_hexing 2013-12-29 15:20:40