这是一个简单的生存游戏, 你控制一个机器人从一个棋盘的起始点 (1,1) 走到棋盘的终点(n,m). 游戏的规则描述如下:
1. 机器人一开始在棋盘的起始点并有起始点所标有的能量.
2. 机器人只能向右或者向下走, 并且每走一步消耗一单位能量.
3. 机器人不能在原地停留.
4. 当机器人选择了一条可行路径后, 当他走到这条路径的终点时, 他将只有终点所标记的能量.
如上图, 机器人一开始在 (1,1) 点, 并拥有 4 单位能量, 蓝色方块表示他所能到达的点, 如果他在这次路径选择中选择的终点是(2,4)
点, 当他到达 (2,4) 点时将拥有 1 单位的能量, 并开始下一次路径选择, 直到到达 (6,6) 点.
我们的问题是机器人有多少种方式从起点走到终点. 这可能是一个很大的数, 输出的结果对 10000 取模.
Input
第一行输入一个整数 T, 表示数据的组数.
对于每一组数据第一行输入两个整数 n,m(1 <= n,m <= 100). 表示棋盘的大小. 接下来输入 n 行, 每行 m 个整数 e(0 <= e <20).
Output
对于每一组数据输出方式总数对 10000 取模的结果.
- Sample Input
- 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
- Sample Output
- 3948
思路: 枚举每一个点, 在每一个点的基础上枚举权值, 把可到达的点都加上当前点的权值
- #include <cstdio>
- #include <map>
- #include <iostream>
- #include<cstring>
- #include<bits/stdc++.h>
- #define ll long long int
- #define M 6
- using namespace std;
- inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
- inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
- int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
- int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
- int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
- const int inf=0x3f3f3f3f;
- const ll mod=1e9+7;
- int n,m;
- int G[107][107];
- int dp[107][107];
- int main(){
- iOS::sync_with_stdio(false);
- int t;
- cin>>t;
- while(t--){
- memset(dp,0,sizeof(dp));
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- cin>>G[i][j];
- dp[1][1]=1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++){
- int t=G[i][j];
- for(int ii=0;ii<=t;ii++)
- for(int jj=0;jj<=t;jj++){
- if(ii+jj==0) continue;
- if(ii+jj>t) break;
- int dx=i+ii;
- int dy=j+jj;
- if(dx<=n&&dy<=m)
- dp[dx][dy]=(dp[dx][dy]%10000+dp[i][j]%10000)%10000;
- }
- }
- cout<<dp[n][m]%10000<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2958591.html