首页 > 代码库 > hdu 1978 记忆化搜索
hdu 1978 记忆化搜索
注意:
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; }
hdu 1978 记忆化搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。