HDU1978 记忆化搜索

HDU1978 记忆化搜索

How many ways Problem Description 这是一个简单的生存游戏，你控制一个机器人从一个棋盘的起始点(1,1) 走到棋盘的终点(n,m) 。游戏的规则描述如下： 1. 机器人一开始在棋盘的起始点并有起始点所标有的能量。 2. 机器人只能向右或者向下走，并且每走一步消耗一单位能量。 3. 机器人不能在原地停留。

4. 当机器人选择了一条可行路径后，当他走到这条路径的终点时，他将只有终点所标记的能量。

如上图，机器人一开始在(1,1) 点，并拥有4 单位能量，蓝色方块表示他所能到达的点，如果他在这次路径选择中选择的终点是(2,4) 点，当他到达(2,4) 点时将拥有1 单位的能量，并开始下一次路径选择，直到到达(6,6) 点。 我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数，输出的结果对10000 取模。

Input 第一行输入一个整数T, 表示数据的组数。 对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100) 。表示棋盘的大小。接下来输入n 行, 每行m 个整数e(0 <= e < 20) 。

Output 对于每一组数据输出方式总数对10000 取模的结果. Sample Input 1 6 6 4 5 6 6 4 3 2 2 3 1 7 2 1 1 4 6 2 7 5 8 4 3 9 5 7 6 6 2 1 5 3 1 1 3 7 2 Sample Output 3948 记忆化搜索 ,dp[i][j] 表示 i 行 j 列的到终点的方法数 .

#include #include #include using namespace std;int n,m,dp[105][105],a[105][105];int check(int x,int y){ if(x<1 || x>n || y<1 || y>m) return 1; return 0;}int dfs(int x,int y){ if(dp[x][y]>=0) return dp[x][y]; dp[x][y] = 0; int i,j; for(i = 0; i<=a[x][y]; i++) for(j = 0; j<=a[x][y]-i; j++) { if(check(x+i,y+j)) continue; dp[x][y] = (dp[x][y]+dfs(x+i,y+j))%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",&a[i][j]); memset(dp,-1,sizeof(dp)); dp[n][m] = 1; printf("%d\n",dfs(1,1)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。