HDU 1078 FatMouse and Cheese

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1078

解题思路：

简单的记忆化搜索。

实现代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=500;
int a[MAXN][MAXN],mark[MAXN][MAXN];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,k;

int dfs(int x,int y){
    if(mark[x][y])
        return mark[x][y];

    int ans=0;
    for(int i=1;i<=k;i++)
    for(int j=0;j<4;j++){
        int xx=x+dx[j]*i;
        int yy=y+dy[j]*i;
        if(xx<n&&xx>=0&&y<n&&y>=0&&a[x][y]<a[xx][yy]){
            ans=max(ans,dfs(xx,yy));
        }
    }
    return mark[x][y]=ans+a[x][y];
}

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