有一種遊戲是的玩法是這樣的：
有一個n*n的格子,每個格子有一個數字。
遵循以下規則:
1. 玩家每次可以由所在格子向上下左右四個方向進行直線移動，每次移動的距離不得超過m
2. 玩家一開始在第一行第一列，并且已經獲得該格子的分值
3. 玩家獲得每一次移動到的格子的分值
4. 玩家下一次移動到達的格子的分值要比目前玩家所在的格子的分值要大。
5. 遊戲所有數字加起來也不大，保證所有數字的和不會超過int型整數的範圍
6. 玩家僅能在n*n的格子内移動，超出格子邊界屬于非法操作
7. 當玩家不能再次移動時，遊戲結束
現在問你，玩家所能獲得的最大得分是多少？
Input有多組測試資料
每組測試樣例第一行是兩個整數n,m (1≤n≤100)(1≤m≤100),當n和m都是-1時為程式結束标志，直接退出即可
之後n行，每行n個數字，描述n*n的格子裡的數字
Output對于每組測試資料輸出一行，這一行僅有一個整數，代表玩家所能獲得的最高得分
Sample Input
3 1
1 2 5
10 11 6
12 12 7
-1 -1 Sample Output
37
分析：
一開始用了一個tle的方法：從原點開始神搜，搜一步松弛一下，這樣就會導緻很多重複的搜尋，但是松弛效率并不高（這一條路松了一遍，另外一條路仍然可能再松一遍），就導緻逾時了。
正解是用dp[i][j]表示從i，j出發所能得到的cheese的最大值，這樣遇到非零的dp[i][j]的時候就可以直接用了（因為dp[i][j]已經是最優解了）。
代碼：
tle代碼：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int maxn = 110;
6 typedef pair<int, int> PAIR;
7
8 int n, m;
9 int res;
10 int chart[maxn][maxn];
11 int dp[maxn][maxn];
12 PAIR dir[5] = { {0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
13
14 void dfs(int x, int y)
15 {
16 for(int i = 1; i <= m; i++)
17 for (int j = 1; j <= 4; j++)
18 {
19 int xx = x + dir[j].first * i, yy = y + dir[j].second * i;
20 if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && chart[xx][yy] > chart[x][y])
21 {
22 if (dp[xx][yy] < dp[x][y] + chart[xx][yy])
23 {
24 dp[xx][yy] = dp[x][y] + chart[xx][yy];
25 res = max(res, dp[xx][yy]);
26 }
27 dfs(xx, yy);
28 }
29
30 }
31 }
32
33 int main()
34 {
35 while (cin >> n >> m && m != -1 && n != -1)
36 {
37 for (int i = 1; i <= n; i++)
38 for (int j = 1; j <= n; j++)
39 scanf("%d", &chart[i][j]);
40 memset(dp, 0, sizeof(dp));
41 res = 0;
42 dp[1][1] = chart[1][1];
43 dfs(1, 1);
44 cout << res << endl;
45 }
46 } 正解代碼：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int maxn = 110;
6 typedef pair<int, int> PAIR;
7
8 int n, m;
9 int res;
10 int chart[maxn][maxn];
11 int dp[maxn][maxn];
12 PAIR dir[5] = { {0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
13
14 int dfs(int x, int y)
15 {
16 if (!dp[x][y])
17 {
18 int res = 0;
19 for (int i = 1; i <= m; i++)
20 for (int j = 1; j <= 4; j++)
21 {
22 int xx = x + dir[j].first * i, yy = y + dir[j].second * i;
23 if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && chart[xx][yy] > chart[x][y])
24 res = max(res, dfs(xx, yy));
25 }
26 dp[x][y] = chart[x][y] + res;
27 }
28 return dp[x][y];
29 }
30
31 int main()
32 {
33 while (cin >> n >> m && m != -1 && n != -1)
34 {
35 for (int i = 1; i <= n; i++)
36 for (int j = 1; j <= n; j++)
37 scanf("%d", &chart[i][j]);
38 memset(dp, 0, sizeof(dp));
39 cout << dfs(1, 1) << endl;
40 }
41 }