hdu 1078 FatMouse and Cheese 记忆化搜索

  一开始打算正向用状态dp，结果果断超时，换成反向记忆话搜索就过了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int map[105][105];
int n,k;
int dp[105][105];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int ans;
int walk(int x,int y)
{
    if(dp[x][y])return dp[x][y];
    int i,j;
    int nx,ny,t=0;
    for(i=0;i<4;i++)
    {
      nx=x;ny=y;
      for(j=0;j<k;j++)
      {
        nx+=dir[i][0];ny+=dir[i][1];
        if(nx<=0||ny<=0||nx>n||ny>n)break;
        if(map[nx][ny]>map[x][y])
            t=max(t,walk(nx,ny));
      }
    }
    dp[x][y]=t+map[x][y];
    return dp[x][y];
}
int main()
{
    while(~scanf("%d%d",&n,&k)&&n+1)
    {
        memset(map,-1,sizeof(map));
        memset(dp,0,sizeof(dp));
        int i,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
               scanf("%d",&map[i][j]);
            }
        printf("%d\n",walk(1,1));
    }
}