一只老鼠在一个ｎ＊ｎ的地图上吃食物，每次只能垂直或者水平走，且所走的格子上的食物必须大于当前所在格子的食物，每次前进，可以只走一格，也可以跳着走ｋ格，最大不能超过ｋ，问你老鼠所能吃到的食物是多少．

DP 跟 DFS 的结合，定义dp[x][y]为走到坐标(x, y)所能吃到的最大食物，那么就可以有 dp[x][y] = max(dp[nx][ny] | nx, ny 为从ｘ出发所有能到达点的坐标) + map[x][y].用 DFS 就可以把问题解决了，最后答案就是 dp[1][1]，表示从初始位置出发所能吃到的最大食物量．

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

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int a[N][N];
int dp[N][N];
int n, k;
int dfs(int x, int y)
{
    if (dp[x][y])
        return dp[x][y];
    int mx = 0;
    for (int i = 1; i <= k; i++) {
        for (int z = 0; z < 4; z++) {
            int nx = x + dx[z] * i, ny = y + dy[z] * i;
            if (1 <= nx && nx <= n && 1 <= ny && ny <= n) {
                if (a[nx][ny] > a[x][y]) {
                    mx = max(mx, dfs(nx, ny));
                }
            }
        }
    }
    return dp[x][y]  = a[x][y] + mx;
}
int main()
{
    while (~scanf("%d %d", &n, &k) && (n != -1 && k != -1)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        printf("%d\n", dfs(1, 1));
    }
    return 0;
}