首页 > 试题广场 >

方案数量

[编程题]方案数量
  • 热度指数：1243 时间限制：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

说明

对于样例一的十条路径如下：
算法知识视频讲解
添加回答
寒冰-侠客头像 寒冰-侠客
能量限制为20，暴力检查满足条件的上一步。 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t,n,m,a[105][105],dp[105][105];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,k,l;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            cin>>a[i][j];
        memset(dp,0,sizeof dp);
        dp[1][1]=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(i==1&&j==1)
                    continue;
                for(k=i;k>=i-20&&k>=1;k--)
                {
                    for(l=j;l>=j-20&&l>=1;l--)
                        if(i-k+j-l<=a[k][l])
                         dp[i][j]=(dp[i][j]+dp[k][l])%10000;
                }
            }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}


发表于 2021-05-02 18:57:02 回复(0)
Syz_cannot头像 Syz_cannot 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int xi[4]={-1,1,0,0};
int yi[4]={0,0,-1-1};
class node{
public:
    int x;
    int y;
    int z;
    node(int a,int b,int c){ x=a;y=b;z=c;}
};
int f[255][101][101];
int main() {
    memset(f,0,sizeof(f));
    int t;
    cin>>t;
    for (int tt=0;tt<t;tt++){
        int n,m;
        cin>>n>>m;
        vector<vector<int>> ma(n,vector<int>(m));
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                cin>>ma[i][j];
            }
        }


        int p=ma[0][0];
        int edx=n-1; int edy=m-1;
        node now(0,0,0);
        f[0][0][0]=1;
        queue<node> q;
        q.push(now);
        while (!q.empty()) {
            node tmp = q.front();
            q.pop();
            int k = ma[tmp.x][tmp.y];
            int st=tmp.z;
            for (int i = tmp.x; i <= min(tmp.x + k, n-1); i++) {
                for (int j = tmp.y; j <= min(tmp.y+ k-( i-tmp.x ), m-1); j++) {
                    if ((i + j - tmp.x - tmp.y >= 1) && (i + j - tmp.x - tmp.y <= k)) {
                        q.push(node(i, j,st+1));
                        f[st+1][i][j] = f[st+1][i][j]+f[st][tmp.x][tmp.y];
                        f[st+1][i][j] %= 10000;
                    }
                }
            }
        }
        int ans=0;
        for (int i=0;i<250;i++){
            ans+=f[i][edx][edy];
            ans%=10000;
        }
        cout<<ans<<endl;
    }
    return 0;
}
想知道为什么bfs不对，有没有大神告诉一下我
发表于 2022-03-18 21:46:17 回复(1)
梦里啥都有头像 梦里啥都有 
#include<bits/stdc++.h> 
using namespace std;
int n, m;


int dpSolution(vector<vector<int>>& nums) {
    vector<vector<int>> dp(n, vector<int>(m, 0));
    dp[0][0] = 1;  //从 [0, 0]走到 [0, 0]的方案数
    for(int i = 0; i < n; i++) {
        for(int j = 0;j < m; j++) {
            
            int e = nums[i][j];
            for(int dx = 0;dx <= e; dx++) {
                for(int dy = 0; dy <= e-dx; dy++) {
                    if(dx == 0 && dy == 0) continue;
                    int nx = i+dx, ny = dy+j;
                    if(nx < n && ny < m) {
                        dp[nx][ny] = (dp[i][j] + dp[nx][ny])%10000;
                    }
                }
            }
        }
    }
    return dp[n-1][m-1];
}

int main(){
    int t;
    cin>>t;
    while(t--) {
        cin >> n >> m;
        vector<vector<int>> nums(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> nums[i][j];
            }
        }
        int res = dpSolution(nums);
        cout << res << endl;
    }
}


编辑于 2022-03-08 21:13:12 回复(0)
kiyoxi头像 kiyoxi
python dp解法：从右下角开始逐行扫描往上走
import sys

def func(data):
    n, m = len(data), len(data[0])
    paths = [[0]*m for _ in range(n)]
    paths_sum = [[0]*m for _ in range(n)]
    for i in range(n-1,-1,-1):
        for j in range(m-1,-1,-1):
            if i==n-1 and j==m-1:
                paths[i][j] = 1
                paths_sum[i][j] = 1
            else:
                st1 = j+1
                ed1 = j+data[i][j]+1
                if st1<m and ed1 < m:
                    paths[i][j] += (paths_sum[i][st1]-paths_sum[i][ed1])
                elif st1<m:
                    paths[i][j] += paths_sum[i][st1]
                st1 = j
                for k in range(i+1, i+data[i][j]+1, 1):
                    if k<n:
                        ed1 -= 1
                        if ed1 < m:
                            paths[i][j] += (paths_sum[k][st1]-paths_sum[k][ed1])
                        else:
                            paths[i][j] += paths_sum[k][st1]
                if j+1<m:
                    paths_sum[i][j] = paths[i][j] + paths_sum[i][j+1]
                else:
                    paths_sum[i][j] = paths[i][j]
    return (paths[0][0])%10000
                


T = int(sys.stdin.readline().strip())
for _ in range(T):
    n, m = [int(i) for i in sys.stdin.readline().strip().split(' ')]
    data = []
    for _ in range(n):
        t = [int(i) for i in sys.stdin.readline().strip().split(' ')]
        data.append(t)
    print(func(data))


编辑于 2021-07-31 14:55:47 回复(0)
黄_昏头像 黄_昏
用BFS超时，还是得用动态规划。 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int T = in.nextInt();
        for(int i=0; i<T; i++){
            int n = in.nextInt();
            int m = in.nextInt();
            Nodee[][] A = new Nodee[n][m];
            for(int j=0; j<n; j++)
                for(int k=0; k<m; k++)
                    A[j][k] = new Nodee(j,k,in.nextInt());

            int[][] dp = new int[n][m];
            dp[0][0] = 1;
            for(int j=0; j<n; j++){
                for(int k=0; k<m; k++){
                    int ener = A[j][k].val;
                    for(int x=j; x<=j+ener && x<n; x++){                        
                        for(int y=k; x-j+y-k<=ener && y<m; y++){
                            if(x==j && y==k)
                                continue;
                            else{
                                dp[x][y] += dp[j][k];
                                dp[x][y] %= 10000;
                            }
                        }
                    }
                }
            }
            System.out.println(dp[n-1][m-1]);            
        }
    }
}

class Nodee{
    public int x;
    public int y;
    public int val;
    public Nodee(int i, int j, int val){
        this.x = i;
        this.y = j;
        this.val = val;
    }
}


发表于 2023-04-01 20:19:57 回复(0)
Python
__kk__头像 __kk__
DFS + 记忆化搜索 

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))
    


发表于 2022-03-08 16:28:44 回复(0)
Java
zjytrhy头像 zjytrhy

本来想用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];
    }
}
编辑于 2021-10-04 12:55:51 回复(0)
眯妈_XJC头像 眯妈_XJC
暴力从0，0向后累加 
#include<iostream>
#include<vector>
using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> tensor(n , vector<int>(m , 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> tensor[i][j];
			}
		}
		int acc = 1;
		vector<vector<int>> arrived(n, vector<int>(m, 0));
		arrived[0][0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				
				
				for (int p = i; p <= i + tensor[i][j]; p++) {
					for (int q = j; q <= j + tensor[i][j]; q++) {
						if (p < n && q < m && p + q - i - j <= tensor[i][j] && (p != i || q != j)) {
							arrived[p][q] += arrived[i][j] % 10000;
						}
					}
				}

			}
		}
		cout << arrived[n - 1][m - 1] % 10000 << '\n';
	}
}

发表于 2021-08-31 22:29:47 回复(0)
JCoder头像 JCoder
预处理出每个格子可以走到哪里，dp转移的时候会稍微方便点 
#include <bits/stdc++.h>
using namespace std;

int n, m, T, a[105][105];
vector<pair<int, int> > pre[105][105];
int dp[105][105];
void color(int x, int y) {
    int cnt = a[x][y];
    for (int i = x; i <= x + a[x][y]; i++) {
        for (int j = y; j <= y + cnt; j++) {
            if (i == x && j == y) {continue;}
            if (i >= n || j >= m) {continue;}
            pre[i][j].push_back(make_pair(x, y));
        }
        cnt--;
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                pre[i][j].clear();
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &a[i][j]);
                color(i, j);
            }
        }

        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) {continue;}
                dp[i][j] = 0;
                for (int k = 0; k < pre[i][j].size(); k++) {
                    dp[i][j] += dp[pre[i][j][k].first][pre[i][j][k].second];
                    dp[i][j] %= 10000;
                }
            }
        }

        printf("%d\n", dp[n - 1][m - 1] % 10000);

    }



    return 0;
}


发表于 2021-08-27 14:07:53 回复(0)
Java
赤埋头像 赤埋
dp不难想 主要是要处理好helper方法中那个循环 
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;
                }
            }
        }
    }
}


发表于 2021-07-28 12:19:59 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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