有这样的一个方格游戏：这个游戏是这样的：
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
对于样例一的十条路径如下：
本来想用bfs的，结果超过队列的最大容量了，用动态规划就行
import java.util.Scanner;
public class Main {
static int n, m;
final static int mod = 10000;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int T = s.nextInt();
for (int times = 0; times < T; times++) {
n = s.nextInt();
m = s.nextInt();
int[][] board = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] = s.nextInt();
}
}
int ans = dpHandle(board);
System.out.println(ans);
}
}
private static int dpHandle(int[][] board) {
int[][] dp = new int[n][m];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int energy = board[i][j];
//i：能够消耗的能量
for (int useEnergy = 1; useEnergy <= energy; useEnergy++) {
//x消耗的能量
for (int xCost = 0; xCost <= useEnergy; xCost++) {
int nx = i, ny = j;
nx += xCost;
ny += useEnergy - xCost;
if (nx >= n || ny >= m) {
continue;
}
dp[nx][ny] = (dp[nx][ny] + dp[i][j]) % mod;
}
}
}
}
return dp[n - 1][m - 1];
}
}
import java.util.Scanner;
import java.lang.System;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
int[][] nums = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
nums[i][j] = sc.nextInt();
}
}
// 调用方法
System.out.println(routeSloves(nums) % 10000);
}
}
private static int routeSloves(int[][] nums) {
int n = nums.length, m = nums[0].length;
int[][] dp = new int[n][m];
dp[0][0] = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
helper(dp, nums[i][j], i , j);
}
}
return dp[n - 1][m - 1];
}
private static void helper(int[][] dp, int hp, int i, int j) {
if(hp <= 0) return;
for(int a = 0; a <= hp; a++) {
for(int b = 0; a + b <= hp; b++) {
if(a == 0 && b == 0) continue;
if(i + a < dp.length && j + b < dp[0].length) {
dp[i + a][j + b] += dp[i][j] % 10000;
}
}
}
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
