有这样的一个方格游戏：这个游戏是这样的：
1.有个方格，方格内每一个位置都有一个数，代表到达这个点后拥有的能量。
2.初始的时候在左上角，并将左上角的值作为初始能量，终点为右下角的点。
3.每一步只能往下或者往右走，且走一步需要消耗点能量。不能在原地停留，即不会获得中间节点的能量并且能量不累计。
4.当你选择了一条可行的路径（这条路径消耗的能量不超过现有能量），你可以走到终点。
例如：
现在想问你有多少条不同的路径（两条路径如果按顺序依次到达的点有一个不同，则认为是不同的路径方式）可以从左上角的点走到右下角的点，由于答案很大，请答案对取余。
输入第一行有一个整数，代表接下来有
对于每一组测试数据第一行输入两个整数和
，
代表方格的大小。接下来
保证每一个文件内和
的总和不超过
对于每组数据输出一行，代表可以走到的方案数量。
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
对于样例一的十条路径如下：
def check(i,j): return i>=0 and i<n and j>=0 and j<m def DFS(x, y): if dp[x][y]: return dp[x][y] else: result = 0 for energy in range(1, arr[x][y]+1): sum_ij = (x+y) + energy for i in range(x, sum_ij-y+1): j = sum_ij - i if check(i,j): num_path = DFS(i,j) dp[i][j] = num_path result = (result + num_path) % MOD return result MOD = 10000 T = int(input()) for _ in range(T): arr = [] n,m = list(map(int, input().split())) for _ in range(n): arr.append(list(map(int, input().split()))) if n==1 and m==1: print(1) else: dp = [[None]*m for _ in range(n)] dp[n-1][m-1] = 1 print(DFS(0,0))
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
