FatMouse and Cheese
题目
有一种游戏是的玩法是这样的：
有一个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
解题思路
下面是来自一个小菜的emmm的思想：我原本还以为这道题把之前那题的代码改一改就好了，记录一下，然后就perfect了。结果不出所料，（pia!pia!pia)后来仔细看看题，发现他往一个方向可以走好多步，不超过k步就行。然后，我又改了改，咦~又WA了！~接下来就是一个描摹代码的过程：把方向数组改掉，比较走的步数，记忆化搜索。
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,k;
int dp[102][102];
int ma[102][102];
int dfs(int a,int b)
{
if(dp[a][b]) return dp[a][b];
dp[a][b]=ma[a][b];
for(int i=1;i<=k;i++)
{
if(a+i<n&&ma[a+i][b]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a+i,b)+ma[a][b]);
if(a-i>=0&&ma[a-i][b]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a-i,b)+ma[a][b]);
if(b+i<n&&ma[a][b+i]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a,b+i)+ma[a][b]);
if(b-i>=0&&ma[a][b-i]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a,b-i)+ma[a][b]);
}
return dp[a][b];
}
int main()
{
while(cin>>n>>k)
{
memset(dp,0,sizeof(dp));
if(n==-1&&k==-1) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>ma[i][j];
}
cout<<dfs(0,0)<<endl;
}
return 0;
}
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,k;
int dp[102][102];
int ma[102][102];
int dfs(int a,int b)
{
if(dp[a][b]) return dp[a][b];
dp[a][b]=ma[a][b];
for(int i=1;i<=k;i++)
{
if(a+i<n&&ma[a+i][b]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a+i,b)+ma[a][b]);
if(a-i>=0&&ma[a-i][b]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a-i,b)+ma[a][b]);
if(b+i<n&&ma[a][b+i]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a,b+i)+ma[a][b]);
if(b-i>=0&&ma[a][b-i]>ma[a][b])
dp[a][b]=max(dp[a][b],dfs(a,b-i)+ma[a][b]);
}
return dp[a][b];
}
int main()
{
while(cin>>n>>k)
{
memset(dp,0,sizeof(dp));
if(n==-1&&k==-1) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>ma[i][j];
}
cout<<dfs(0,0)<<endl;
}
return 0;
}
