hdu 1978 记忆化搜索
搜索 HDU 记忆
2023-09-11 14:14:09 时间
注意:
dp【i】【j】 表示(i,j)这个点有多少种方式 mark【i】【j】表示这个点是否走过 假设有直接返回dp【i】【j】 dp的求法为全部梦走到点的dp的和
注意mark開始的标记
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int dp[110][110],mark[110][110],cost[110][110],n,m; int dfs(int x,int y) { int i,j; if(mark[x][y]) return dp[x][y]; //dp[x][y]=0; for(i=0;i<=cost[x][y];i++) { for(j=0;j<=cost[x][y]-i;j++) { int xx=x+i; int yy=y+j; if(xx<=0||xx>n||yy<=0||yy>m) continue; if(mark[xx][yy]==0) { mark[x][y]=1; dfs(xx,yy); } dp[x][y]=(dp[x][y]+dp[xx][yy])%10000; } } return dp[x][y]; } int main() { int T,i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&cost[i][j]); memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); dp[n][m]=1; mark[n][m]=1; printf("%d\n",dfs(1,1)); } return 0; }
相关文章
- Java实现 LeetCode 240 搜索二维矩阵 II
- 顶部搜索框背景色渐变
- SAP Fiori的搜索实现
- 扇区搜索机制的果蝇优化算法-附代码
- 【搜索】 HDU 3533 Escape BFS 预处理
- 449. 序列化和反序列化二叉搜索树-前序遍历法
- 百度举办移动搜索全国巡回沙龙,为移动互联网注入新活力
- [搜索] hdu 4016 Magic Bitwise And Operation
- dreamwaver的动态相关文件 工具栏搜索
- 进程注入分析实战——通过process explorer可以看到lab12-01.dll在运行时加载了, 要查看dll被哪个进程所使用,可以在process explorer里搜索!
- ES 搜索结果expalain 可以类似数据库性能调优来看排序算法的选择