摘要：
含义：给定n*n网格，每个网格中都有一些食物。值得记住的是，当老鼠每次走k步时，它可以吃最多的食物。它已经被重写了n次。在之前的搜索中没有注意到的一个小地方导致了重复的ac代码：#include#incluse #include＜string h＞使用namespacestd；intdp[110][110]，s[110][110]；整数n，k，t[4][2]={1,0，-1,0,0,1,0，-1}；Intdfs｛intmaxx=0，xx，yy，ans；if（！Dp[x][y]）｛for｛for{xx=x+t[j][0]*i；yy=y+t[j][1]*i；if//这是错误的。您不能首先判断s[xx][yy]，否则re｛ans=dfs；ifmaxx=ans；｝｝将出现Dp[x][y]=maxx+s[y]；｝返回dp[x][y]；}intmain（）｛当｛ifbreak；forforscanf；memset；intsum＝dfs（0,0）；printf；｝返回0；｝
题意：给出n*n的格子，每个各自里面有些食物，问一只老鼠每次走最多k步所能吃到的最多的食物
这道题目，值得我记住它，re了n次，以前写搜索没有注意的一个小地方，导致re这么多次的
ac代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[110][110],s[110][110];
int n,k,t[4][2]={1,0,-1,0,0,1,0,-1};
int dfs(int x,int y)
{
int maxx=0,xx,yy,ans;
if(!dp[x][y])
{
for(int i=1;i<=k;i++)
{
for(int j=0;j<4;j++)
{
xx=x+t[j][0]*i;
yy=y+t[j][1]*i;
if(xx>=0&&xx<n&&yy>=0&&yy<n&&s[xx][yy]>s[x][y])
{
ans=dfs(xx,yy);
if(ans>maxx)
maxx=ans;
}
}
}
dp[x][y]=maxx+s[x][y];
}
return dp[x][y];
}
int main()
{
while(scanf("%d%d",&n,&k)>0)
{
if(n==-1&&k==-1)
break;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&s[i][j]);
memset(dp,0,sizeof(dp));
int sum=dfs(0,0);
printf("%d
",sum);
}
return 0;
}
re代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[110][110],s[110][110];
int n,k,t[4][2]={1,0,-1,0,0,1,0,-1};
int dfs(int x,int y)
{
int maxx=0,xx,yy,ans;
if(!dp[x][y])
{
for(int i=1;i<=k;i++)
{
for(int j=0;j<4;j++)
{
xx=x+t[j][0]*i;
yy=y+t[j][1]*i;
if(s[xx][yy]>s[x][y]&&xx>=0&&xx<n&&yy>=0&&yy<n) //这里错了，不能将s[xx][yy]先判断，否则出现re
{
ans=dfs(xx,yy);
if(ans>maxx)
maxx=ans;
}
}
}
dp[x][y]=maxx+s[x][y];
}
return dp[x][y];
}
int main()
{
while(scanf("%d%d",&n,&k)>0)
{
if(n==-1&&k==-1)
break;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&s[i][j]);
memset(dp,0,sizeof(dp));
int sum=dfs(0,0);
printf("%d
",sum);
}
return 0;
}