hdu1078 zoj1107(记忆化搜索/DP)
搜索 记忆 DP
2023-06-13 09:12:45 时间
大家好,又见面了,我是你们的朋友全栈君。
题目链接:zoj hdu
题目大意:老鼠从(0,0)出发,每次在同一个方向上最多前进k步,且每次到达的位置上的数字都要比上一个位置上的数字大,求老鼠经过的位置上的数字的和的最大值
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int n;
int k;//前进的步数
int map[105][105];
int ans[105][105];//记忆化搜索,保存中间搜索结果
int search(int x,int y)
{
int dx,dy;//要去的下一个位置
int i,maxx = 0;
if(ans[x][y] != -1) return ans[x][y];//已经搜索过,直接返回结果
for(i = 1 ; i <= k ; i ++)//向前走的步数
{
dx = x - i;//向上
if(dx >= 0 && dx < n && map[dx][y] > map[x][y])
{
ans[dx][y] = search(dx,y);
maxx = max(maxx,ans[dx][y]);
}
dx = x + i;//向下
if(dx >= 0 && dx < n && map[dx][y] > map[x][y])
{
ans[dx][y] = search(dx,y);
maxx = max(maxx,ans[dx][y]);
}
dy = y - i;//向左
if(dy >= 0 && dy < n && map[x][dy] > map[x][y])
{
ans[x][dy] = search(x,dy);
maxx = max(maxx,ans[x][dy]);
}
dy = y + i;//向右
if(dy >= 0 && dy < n && map[x][dy] > map[x][y])
{
ans[x][dy] = search(x,dy);
maxx = max(maxx,ans[x][dy]);
}
}
return maxx + map[x][y];
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&k) && (n != -1 && k != -1))
{
for(i = 0 ; i < n ; i ++)
for(j = 0 ; j < n ; j ++)
scanf("%d",&map[i][j]);
memset(ans,-1,sizeof(ans));
printf("%d\n",search(0,0));
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/164454.html原文链接:https://javaforall.cn
相关文章
- 论记忆化搜索
- 记忆化搜索(递归)讲解「建议收藏」
- leetcode-91解码方法(动态规划|记忆化搜索)[通俗易懂]
- 手写一个二叉搜索树(BST)
- 【生信教程】如何搜索高速下载一篇CancerCell文章中测序原始文件,B站有视频教程哦~
- 跨平台极速文件搜索工具,终于找到了!
- AI与搜索的双螺旋:取之于搜索,用之于搜索
- 【综合笔试题】难度 3.5/5,括号相关剪枝搜索题
- 浅谈微博话题爬虫关键词 and or 语法搜索
- 数据结构实验之图论一:基于邻接矩阵的广度优先搜索遍历 (SDUT 2141)
- 搭建一个可搜索的网页文件服务器(即52破解爱盘)
- 用Solr优化MySQL,提高搜索效率(solrmysql)
- 用ASP将SQL搜索出来的内容导出为TXT的代码
- ajax+php谷歌搜索框自动填充功能实例代码
- php+ajax做仿百度搜索下拉自动提示框(有实例)