A25180. 弹球游戏
填空题
容易
知识点
题目描述
弹球游戏
题目描述：
有一个弹球游戏，游戏由 n 行 m 列的网格组成，除最后一行的网格外，其余每个网格中都有一个元素（仙人掌、旋风或地洞）。将弹球投向第一行的网格，弹球到达不同的元素网格会有不同的效果：
（1）到达仙人掌网格：弹球被粘住，无法再移动；
（2）到达旋风网格：弹球可被吹向相邻的三个网格之一：左下、正下、右下，若某个方向无相邻网格，则不吹向该方向；
（3）到达地洞网格：弹球被向下传送两个网格，若超出网格范围，则传送到地洞正下方相邻的网格。
给定网格的行数 n 和列数 m，以及每个网格中的元素类型，请计算弹球从第一行到达最后一行的网格有多少条路线。
例如：n = 3，m = 3；3 行 3 列的网格如下图所示：
弹球一共有 4 条路线到达最后一行：
输入描述：
第一行输入两个整数 n、m（3≤n，m≤100），表示弹球游戏中网格的行数和列数，整数之间以一个空格隔开；
接下来输入 n - 1 行，表示第 1 行到第 n - 1 行的网格情况，每行 m 个整数，整数只能为 1、2、3；
1 表示该网格元素是仙人掌、2 表示该网格元素是旋风，3 表示该网格元素是地洞，同一行的整数之间以一个空格隔开；
最后一行输入 m 个 0，0 表示该网格是第 n 行（最后一行）的网格，整数之间以一个空格隔开。
输出描述：
输出一个整数，表示弹球从第一行到达最后一行的网格有多少条路线。
样例输入：
3 3
1 2 3
3 1 2
0 0 0 样例输出：
4参考答案
#include <iostream>
using namespace std;
int a[3][100], dp[3][100] = {0}; //dp[i][j]表示从(i,j)出发到达最后一行的路线数
int main() {
int n, m, s = 0;
cin >> n >> m;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> a[i][j];
}
}
for(int j=0; j<m; j++) {
dp[n-1][j] = 1; //最后一行所有位置路线数为1
}
//从倒数第二行开始向上递推
for(int i=n-2; i>=0; i--) {
for(int j=0; j<m; j++) {
if(a[i][j] == 1) {//仙人掌
dp[i][j] = 0;
} else if(a[i][j] == 2) { //旋风
int cnt = 0;
if(j-1>=0) //左下
cnt += dp[i+1][j-1];
if(j+1<m) //右下
cnt += dp[i+1][j+1];
cnt += dp[i+1][j]; //正下
dp[i][j] = cnt;
} else if(a[i][j] == 3) { //地洞
if(i+2<n) {
dp[i][j] = dp[i+2][j];
} else {
//超出范围，传送到正下方
dp[i][j] = dp[i+1][j];
}
}
}
}
for(int j=0; j<m; j++) { //第一行的总和即为答案
s += dp[0][j];
}
cout << s << endl;
return 0;
}
上一题
下一题