首页 > 试题广场 > 方案数量
[编程题]方案数量
  • 热度指数:14 时间限制: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)