HDU1078--FatMouse and Cheese（dp+dfs，记忆化搜索）

题意：老鼠从（0,0）开始，每次只能往上下左右其中一个方向最多走k步，且每次走到的格子的数字要严格大于当前格子，问能走到的所有数字的和最大是多少。

纯搜索会超时，用dp数组结合dfs进行记忆化搜索，大大减少了无用计算。

dp[i,j]表示从当前格子出发最多能获得的最大值，初始化dp数组为0，每次遍历到点的dp[i,j]不为0时，该点无需再遍历，直接取dp[i,j]的值即可，因为深搜（“不撞南墙不回头”）的性质，遍历到该点之后，会遍历到四个方向都不能走为止，每层return回来的都取max值，故dp[i,j]非0时的值一定是最大值。

代码如下（含注解）：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[150][150];
int a[150][150];//地图; 
int dir[4][2]={1,0,-1,0,0,1,0,-1};//方向数组; 
int ans;
int n,k;
//dp+dfs记忆化搜索:dp[i][j]表示从该点开始能获得的最大值; 

int dfs(int x,int y)
{
	if(dp[x][y]!=0)
	{
		return dp[x][y];//dp[i][j]已经有值表示其已经遍历过了,由于深搜的性质(不撞南墙不回头...), 
	}                  //dp[i][j]记录的就是从(i,j)这点出发所能满足条件的获取的最大值; 
	int i,j;
	int ans=0;//存储当前层的下一层四个方向搜索的最大值; 
	for(i=1;i<=k;i++)
	{
		for(j=0;j<4;j++)
		{
			int nowx=x+dir[j][0]*i;
			int nowy=y+dir[j][1]*i;//if判断:1.是否出界;2.是否满足取值递增的条件; 
			if(nowx>=0&&nowx<n&&nowy>=0&&nowy<n&&a[nowx][nowy]>a[x][y])//取值递增的条件还保证了不用vis数组的情况下 
	        {                                                         //不会回头搜,因为严格递增的传递,目前搜的值不可能 
			    ans=max(ans,dfs(nowx,nowy));                          // 出现比之前同一次dfs已经搜过的值小的情况; 
			}
		}
	}
	return dp[x][y]=ans+a[x][y];
}

int main()
{
	int i,j;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		if(n==-1&&k==-1)
		{
			break;
		}
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		printf("%d\n",dfs(0,0));
	}
	return 0;
}