首页 > 试题广场 >

方案数量

[编程题]方案数量
  • 热度指数：1246 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

有这样的一个方格游戏：这个游戏是这样的：

1.有个方格，方格内每一个位置都有一个数，代表到达这个点后拥有的能量。

2.初始的时候在左上角，并将左上角的值作为初始能量，终点为右下角的点。

3.每一步只能往下或者往右走，且走一步需要消耗点能量。不能在原地停留，即不会获得中间节点的能量并且能量不累计。

4.当你选择了一条可行的路径（这条路径消耗的能量不超过现有能量），你可以走到终点。

例如：

最开始在点，拥有的是点能量，蓝色的方格代表从起点出发步以内所能走到的点，假设我们第一次走到,则到达后能量变为点，那么接下来可以达到的点为和。

现在想问你有多少条不同的路径（两条路径如果按顺序依次到达的点有一个不同，则认为是不同的路径方式）可以从左上角的点走到右下角的点，由于答案很大，请答案对取余。


输入描述:
输入第一行有一个整数，代表接下来有组测试数据。
对于每一组测试数据第一行输入两个整数和，
代表方格的大小。接下来行，每一行输入个数，代表这个方格内的能量。



保证每一个文件内和的总和不超过


输出描述:
对于每组数据输出一行，代表可以走到的方案数量。
示例1

输入

2
3 3
2 1 1
1 1 1
1 1 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

输出

10
3948

说明

对于样例一的十条路径如下：
算法知识视频讲解
开通博客
头像 CUG23届硕士毕业生
发表于 2022-04-11 22:45:44
简单动态规划题 题目简述 n * m 的方格，每一个都有一个能量值，初始在左上角，终点在右下角，初始能量就是起点方格的能量值。每步只能向右或向下走一格，一步消耗1能量，一次可以走若干步，只有一次走完后才更新能量，中间经过的方格能量无效； 每走一次，能量清零，新的初始能量为当前方格的能量值。求有多少种 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 赫he
发表于 2023-05-15 14:04:05
dfs超时，bp可以过 bp:f[a][b]=f[a][b]+f[i][j] 其中(a,b)是(i,j)所能在能量范围内到达的位置，记录该位置能到达几次，到了f[n][m]就是有多少条路径可以到终点。 #include <iostream> #include <vector> 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
10条回答 4894浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号