题目：mouse开始在（0,0）每次可以走1到k格，不能转弯；而且下一格的值要大于这一格
注意：1. ”then runs either horizontally or vertically to another location“ 题目说了 ，不能转弯呀！！！！！又理解错了，，，
2.有个bug找了好长时间，，，dir[4][2]={{},{},{},{}};
for(int i=1;i<=4;i++)//有四个方向
for(int j=1;j<=k;j++)//每次可以选择走1-k步
{
tx=x+j*dir[i][0];
ty=y+j*dir[i][1]; }
是从0开始不是从1 呀！！！！！ 好大只bug呀
3.对深搜理解 不深！！！以后多练习
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<math.h>
using namespace std;
const int maxn=1000;
int maze[maxn][maxn],dp[maxn][maxn];
int n,k;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool inline IN(int x,int y)
{
if(0<=x&&x<n && 0<=y&&y<n)
return true;
else
return false;
}
int dfs(int x,int y)
{
int tx,ty,max=0,temp;
if(dp[x][y]>0)
return dp[x][y];
for(int i=0;i<4;i++)//for(int i=1;i<=4;i++)//有四个方向
for(int j=1;j<=k;j++)//每次可以选择走1-k步
{
tx=x+j*dir[i][0];
ty=y+j*dir[i][1];
if( IN(tx,ty) && maze[x][y]<maze[tx][ty] )
{
temp=dfs(tx,ty);
if(max<temp)
max=temp;
}
}
dp[x][y]=max+maze[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",&maze[i][j]);
memset(dp,0,sizeof(dp));
dfs(0,0);
int ans=dp[0][0];
printf("%d\n",ans);
}
system("pause");
return 0;
}
/*有错误的代码
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<math.h>
using namespace std;
const int maxn=1000;
int maze[maxn][maxn],dp[maxn][maxn];
int n,k;
int inline _abs(int x)
{
if(x<0)
return -x;
}
int dfs(int x,int y)
{
//printf("x= %d y=%d\n",x,y);
if(dp[x][y]!=-1)
return dp[x][y];
int temp;
for(int i=-k;i<=k;i++)
for(int j=-k;j<=k;j++)
{
if( (_abs(i)+_abs(j)<=k) && (0<=x+i&&x+i<n && 0<=y+j&&y+j<n) && maze[x][y]<maze[x+i][y+j] )
{
printf("%d %d\n",i,j);
temp=dfs(x+i,y+j);
if(dp[x][y]<maze[x][y]+temp)
dp[x][y]=maze[x][y]+temp;
}
}
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
break;
int temp=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&maze[i][j]);
if(maze[i][j]>temp)
temp=maze[i][j];
}
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(maze[i][j]==temp)
dp[i][j]=temp;
dfs(0,0);
int ans=dp[0][0]+maze[0][0];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d ",dp[i][j]);
printf("\n");
}
printf("%d\n",ans);
}
system("pause");
return 0;
}
/*
10 11 6
12 12 7
0 1
0 1
1 -1
1 -1
1 0
1 0
0 -1
1 -1
1 0
0 -1
1 -1
0 1
1 0
1 1
1 0
1 1
1 0
1 1
34 31 7
33 23 29
12 12 19
35
*/
/****************************
TLE 的代码。。。。。
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<math.h>
using namespace std;
int _abs(int x)
{
if(x<0)
return -x;
}
const int maxn=1000;
int maze[maxn][maxn],dp[maxn][maxn];
int n,k;
void dfs(int x,int y)
{
for(int i=-k;i<=k;i++)
for(int j=-k;j<=k;j++)
{
if( (_abs(i)+_abs(j)<=k) && (0<=x+i&&x+i<n&&0<=y+j&&y+j<n) && maze[x][y]<maze[x+i][y+j] )
if(dp[x][y]+maze[x+i][y+j]>dp[x+i][y+j])
{
dp[x+i][y+j]=dp[x][y]+maze[x+i][y+j];
dfs(x+i,y+j);
}
}
}
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",&maze[i][j]);
memset(dp,0,sizeof(dp));
dp[0][0]=maze[0][0];
dfs(0,0);
/*for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d ",dp[i][j]);
printf("\n");
}
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(dp[i][j]>ans)
ans=dp[i][j];
printf("%d\n",ans);
}
//system("pause");
return 0;
}
*/