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

题意：每次仅仅能走 横着或竖着的 1~k 个格子。求最多能吃到的奶酪。

代码：

#include <stdio.h>

#include <ctime>

#include <math.h>

#include <limits.h>

#include <complex>

#include <string>

#include <functional>

#include <iterator>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <list>

#include <bitset>

#include <sstream>

#include <iomanip>

#include <fstream>

#include <iostream>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <time.h>

#include <ctype.h>

#include <string.h>

#include <assert.h>

using namespace std;

int n, k;

int a[110][110], dp[110][110];

int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool is_ok(int x, int y)

{

    if (x < 0 || x >= n || y < 0 || y >= n) return false;

    return true;

}

int res(int x, int y)

{

    int sum = 0,tmp = 0;

    if (!dp[x][y])

    {

        for (int i = 1; i <= k; i++)

        {

            for (int j = 0; j < 4; j++)

            {

                int xx = x + dir[j][0] * i;

                int yy = y + dir[j][1] * i;

                if (is_ok(xx,yy) && a[xx][yy] > a[x][y])

                {

                    sum = res(xx, yy);

                    tmp = max(tmp, sum);

                }

            }

        }

        dp[x][y] = tmp + a[x][y];

    }

    return dp[x][y];

}

int main()

{

    while (scanf("%d %d", &n,&k) != EOF)

    {

        if (n == -1 && k == -1) break;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                scanf("%d",&a[i][j]);

        memset(dp, 0, sizeof(dp));

        printf("%d\n", res(0,0));

    }

    return 0;

}