记忆化搜索，FatMouse and Cheese

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1107

http://acm.hdu.edu.cn/showproblem.php?pid=1078

1、从gird[0][0]出发，每次的方向搜索一下，每次步数搜索一下

for(i=0; i<4; i++) {for(j=1; j<=k; j++){int tx=x+d[i][0]*j;int ty=y+d[i][1]*j;if(tx>=0&&tx<n&&ty>=0&&ty<n&&grid[x][y]<grid[tx][ty]){int temp=memSearch(tx,ty);if(max<temp) max=temp;}} }

2、temp不断更新四个方向和每一步走多远的最优值

#include <cstdio> #include <string.h>using namespace std;int n;///网格大小 int k;///每次最多移动的步数 int grid[105][105];///奶酪 int cheese[105][105];///记忆化搜索///方向 int d[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};///记忆化搜 int memSearch(int x,int y) {int i,j;int max=0;if(cheese[x][y]>0) return cheese[x][y];for(i=0; i<4; i++){for(j=1; j<=k; j++){int tx=x+d[i][0]*j;int ty=y+d[i][1]*j;if(tx>=0&&tx<n&&ty>=0&&ty<n&&grid[x][y]<grid[tx][ty]){int temp=memSearch(tx,ty);if(max<temp) max=temp;}}}return cheese[x][y]=max+grid[x][y]; }int main() {while(scanf("%d%d",&n,&k)&&n!=-1&&k!=-1){memset(cheese,0,sizeof(cheese));for(int i=0; i<n; i++){for(int j=0; j<n; j++)scanf("%d",&grid[i][j]);}printf("%d\n",memSearch(0,0));}return 0; }

 

转载于:https://www.cnblogs.com/TreeDream/p/5260237.html

总结

以上是生活随笔为你收集整理的记忆化搜索，FatMouse and Cheese的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。