首页 > 代码库 > hdu 1078 FatMouse and Cheese（记忆搜）
hdu 1078 FatMouse and Cheese（记忆搜）
N*N的矩阵，每个格子上有一个值。
老鼠起始在（1，1），每次只能水平着走或垂直着走。且最多只能走K步。且走到的格子里的值必须比上一次呆的格子里的值大。
问老鼠最多收集到多少值。
思路：
记忆搜好写、方便。
注意边界
代码：
int n,k;int a[105][105];int dp[105][105];int dfs(int x,int y){ if(dp[x][y]>0) return dp[x][y]; for(int i=x+1;i<=min(n,x+k);++i){ if(a[i][y]>a[x][y]){ dp[x][y]=max( dp[x][y],dfs(i,y)+a[x][y] ); } } for(int i=x-1;i>=max(1,x-k);--i){ if(a[i][y]>a[x][y]){ dp[x][y]=max( dp[x][y],dfs(i,y)+a[x][y] ); } } for(int i=y+1;i<=min(n,y+k);++i){ if(a[x][i]>a[x][y]){ dp[x][y]=max( dp[x][y],dfs(x,i)+a[x][y] ); } } for(int i=y-1;i>=max(1,y-k);--i){ if(a[x][i]>a[x][y]){ dp[x][y]=max( dp[x][y],dfs(x,i)+a[x][y] ); } } if(dp[x][y]==0) dp[x][y]=a[x][y]; return dp[x][y];}int main(){ while(scanf("%d%d",&n,&k)!=EOF){ if(n==-1 && k==-1){ break; } rep(i,1,n){ rep(j,1,n){ scanf("%d",&a[i][j]); } } mem(dp,0); int ans=dfs(1,1); printf("%d\n",ans); } return 0;}
hdu 1078 FatMouse and Cheese（记忆搜）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。