Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

记忆化搜索

Posted by 2012201208 at 2013-12-03 11:13:02 on Problem 1088
#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;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator