題意:老鼠從(0,0)開始,每次隻能往上下左右其中一個方向最多走k步,且每次走到的格子的數字要嚴格大于目前格子,問能走到的所有數字的和最大是多少。
純搜尋會逾時,用dp數組結合dfs進行記憶化搜尋,大大減少了無用計算。
dp[i,j]表示從目前格子出發最多能獲得的最大值,初始化dp數組為0,每次周遊到點的dp[i,j]不為0時,該點無需再周遊,直接取dp[i,j]的值即可,因為深搜(“不撞南牆不回頭”)的性質,周遊到該點之後,會周遊到四個方向都不能走為止,每層return回來的都取max值,故dp[i,j]非0時的值一定是最大值。
代碼如下(含注解):
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[150][150];
int a[150][150];//地圖;
int dir[4][2]={1,0,-1,0,0,1,0,-1};//方向數組;
int ans;
int n,k;
//dp+dfs記憶化搜尋:dp[i][j]表示從該點開始能獲得的最大值;
int dfs(int x,int y)
{
if(dp[x][y]!=0)
{
return dp[x][y];//dp[i][j]已經有值表示其已經周遊過了,由于深搜的性質(不撞南牆不回頭...),
} //dp[i][j]記錄的就是從(i,j)這點出發所能滿足條件的擷取的最大值;
int i,j;
int ans=0;//存儲目前層的下一層四個方向搜尋的最大值;
for(i=1;i<=k;i++)
{
for(j=0;j<4;j++)
{
int nowx=x+dir[j][0]*i;
int nowy=y+dir[j][1]*i;//if判斷:1.是否出界;2.是否滿足取值遞增的條件;
if(nowx>=0&&nowx<n&&nowy>=0&&nowy<n&&a[nowx][nowy]>a[x][y])//取值遞增的條件還保證了不用vis數組的情況下
{ //不會回頭搜,因為嚴格遞增的傳遞,目前搜的值不可能
ans=max(ans,dfs(nowx,nowy)); // 出現比之前同一次dfs已經搜過的值小的情況;
}
}
}
return dp[x][y]=ans+a[x][y];
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
{
break;
}
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("%d\n",dfs(0,0));
}
return 0;
}