hdu1078 FatMouse and Cheese —— 记忆化搜索

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078

代码1：

#include<stdio.h>//hdu 1078 记忆化搜索

#include<string.h>

#define MAX(a,b) (a>b?a:b)

int n,k,dp[105][105],a[105][105];

int dfs(int i,int j)

{

    if(dp[i][j]) return dp[i][j];

    dp[i][j] = a[i][j];

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

    {

        if( i+m>=1 && i+m<=n && a[i+m][j]>a[i][j] ) dp[i][j] = MAX(dp[i][j],a[i][j]+dfs(i+m,j));

        if( i-m>=1 && i-m<=n && a[i-m][j]>a[i][j] ) dp[i][j] = MAX(dp[i][j],a[i][j]+dfs(i-m,j));

        if( j+m>=1 && j+m<=n && a[i][j+m]>a[i][j] ) dp[i][j] = MAX(dp[i][j],a[i][j]+dfs(i,j+m));

        if( j-m>=1 && j-m<=n && a[i][j-m]>a[i][j] ) dp[i][j] = MAX(dp[i][j],a[i][j]+dfs(i,j-m));

    }

    return dp[i][j];

}

int main()

{

    while(scanf("%d %d",&n,&k) && (n!=-1 || k!=-1))

    {

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

        for(int j = 1; j<=n; j++)

            scanf("%d",&a[i][j]);

        memset(dp,0,sizeof(dp));

        printf("%d\n",dfs(1,1));

    }

    return 0;

}

代码2：

#include<stdio.h>//hdu 1078 记忆化搜索

#include<string.h>

#define MAX(a,b) (a>b?a:b)

int n,k,dp[105][105],a[105][105],d[4][2] = {1,0,-1,0,0,1,0,-1};

int dfs(int i,int j)

{

    if(dp[i][j]) return dp[i][j];

    dp[i][j] = a[i][j];

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

    for(int m = 0; m<4; m++)

    {

        int x = i+d[m][0]*t, y = j+d[m][1]*t;

        if(x>=1 && x<=n && y>=1 && y<=n && a[x][y]>a[i][j])

            dp[i][j] = MAX(dp[i][j], a[i][j]+dfs(x,y));

    }

    return dp[i][j];

}

int main()

{

    while(scanf("%d %d",&n,&k) && (n!=-1 || k!=-1))

    {

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

        for(int j = 1; j<=n; j++)

            scanf("%d",&a[i][j]);

        memset(dp,0,sizeof(dp));

        printf("%d\n",dfs(1,1));

    }

    return 0;

}