FatMouse and Cheese

3 1
1 2 5
10 11 6
12 12 7
-1 -1

37

普通搜索 会超时的  感觉这道题和滑雪（poj1088,nyoj10）一样  只不过多了一些方向  

首先附上超时代码 +理解错误（He eats up the cheese where he stands and then runs either horizontally or vertically to another location.）

#include <stdio.h>
#include <string.h>
int n,k;
int map[105][105];
bool vis[105][105];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int max;
bool limit(int x1,int y1,int x,int y)
{
    if(vis[x1][y1]||x1<0||y1<0||x1>=n||y1>=n||map[x1][y1]<=map[x][y])
    return false;
    return true;
}
void dfs(int x,int y,int sum)
{
    if(sum>max)
    max=sum;
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<4;j++)
        {
            int x1=x+dir[j][0];
            int y1=y+dir[j][1];
            if(limit(x1,y1,x,y))
            {
                vis[x1][y1]=true;
                sum+=map[x1][y1];
                dfs(x1,y1,sum);
                vis[x1][y1]=false;
                sum-=map[x1][y1];
            }
        }
    }
}
int main()
{
    while(~scanf("%d %d",&n,&k))
    {
        if(n==-1&&k==-1)
        break;
        memset(map,0,sizeof(map));
        memset(vis,false,sizeof(vis));
        if(k>n+n)
        k=n+n;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&map[i][j]);    
        max=0;
        vis[0][0]=true;
        dfs(0,0,map[0][0]);    
        printf("%d\n",max);
    }
    return 0;
}

记忆化搜索：

#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
using namespace std;
int n,k,result;
int map[105][105];
int dp[105][105];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
	int x,y;
};
bool limit(int x1,int y1,int x,int y)
{
    if(x1<0||y1<0||x1>=n||y1>=n||map[x1][y1]<=map[x][y])
    return false;
    return true;
}
int dfs(int x,int y)
{
	if(dp[x][y]) 
	return dp[x][y];
	for(int i=1;i<=k;i++)
	{
		for(int j=0;j<4;j++)
		{
			
			int x1=x+dir[j][0]*i;
			int y1=y+dir[j][1]*i;
			if(limit(x1,y1,x,y))
			{
				int z=dfs(x1,y1);
				if(dp[x][y]<z+map[x1][y1])
				dp[x][y]=z+map[x1][y1];
			}
		}
	}
	return dp[x][y];
}
int main()
{
    while(~scanf("%d %d",&n,&k))
    {
        if(n==-1&&k==-1)
        break;
        result=0;
        memset(map,0,sizeof(map));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&map[i][j]);
        printf("%d\n",dfs(0,0)+map[0][0]);
    }
    return 0;
}

hdu 1078 FatMouse and Cheese(记忆化搜索)

原文：http://blog.csdn.net/su20145104009/article/details/51135611