hdu1078 記憶化搜索

hdu1078 記憶化搜索

題意：

給你n*n的地圖 每個格子有一個值只能從值小的格子走到值較大的格子 給你k每次上下左右最多走k步 問你走的格子最大值的是多少

dp【i】【j】表示以（i，j）為起點的能得到的最大值 然後深搜求解

#include
#include
#include
using namespace std;


int n,k,dp[110][110],cost[110][110];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int mark[110][110];
int max(int a,int b)
{
    return a>b?a:b;
}
int dfs(int x,int y)
{
    int i,j,sum=0;
    for(i=1;i<=k;i++)
    {
        for(j=0;j<4;j++)
        {
            int xx=x+dir[j][0]*i;
            int yy=y+dir[j][1]*i;
            if(xx<0||xx>=n||yy<0||yy>=n) continue;
            if(cost[xx][yy]<=cost[x][y]) continue;
            if(mark[xx][yy])
            {
                sum=max(sum,dp[xx][yy]);
            }
            else 
            {
                mark[xx][yy]=1;
                sum=max(sum,dfs(xx,yy));
            }
        }
    }
    dp[x][y]=cost[x][y]+sum;
    return dp[x][y];    
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&k))
    {
        if(n<0) break;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&cost[i][j]);
        }
        memset(dp,0,sizeof(dp));
        memset(mark,0,sizeof(mark));
        mark[0][0]=1;
        printf("%d\n",dfs(0,0));
    }
    return 0;
}