网站建设代理平台,简历设计网站,有服务器了怎么做网站,网站制作一般要几天[蓝桥杯 2020 省 AB1] 走方格
题目描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样#xff0c;从上到下依次为第 1 1 1 至第 n n n 行#xff0c;从左到右依次为第 1 1 1 至第 m m m 列#xff0c;每一个点可以用行号和列号来表示。
现在有个人…[蓝桥杯 2020 省 AB1] 走方格
题目描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样从上到下依次为第 1 1 1 至第 n n n 行从左到右依次为第 1 1 1 至第 m m m 列每一个点可以用行号和列号来表示。
现在有个人站在第 1 1 1 行第 1 1 1 列要走到第 n n n 行第 m m m 列。只能向右或者向下走。
注意如果行号和列数都是偶数不能走入这一格中。
问有多少种方案。
输入格式
输入一行包含两个整数 n n n m m m。
输出格式
输出一个整数表示答案。
样例 #1
样例输入 #1
3 4样例输出 #1
2提示 1 ≤ n , m ≤ 30 1\le n,m\le30 1≤n,m≤30。
蓝桥杯 2020 第一轮省赛 A 组 G 题B 组 H 题。 思路
首先定义一个二维数组dp其中dp[i][j]表示从网格的左上角(1,1)到当前位置(i,j)的路径数量。dp的大小为(N,N)其中N是一个预设的常数。
接着从输入中读取网格的实际大小n和m。n和m分别表示网格的行数和列数。
然后初始化dp数组的第一行和第一列。由于只能向右或向下走所以从(1,1)到第一行或第一列的任何位置都只有一种走法所以将dp数组的第一行和第一列都设为1。
易知状态转移方程
dp[i][j] dp[i-1][j] dp[i][j-1]接下来使用两个嵌套的for循环遍历dp数组的剩余部分。对于每个位置(i,j)如果行号i和列数j都是偶数则不能走入这个位置所以将dp[i][j]设为0。否则从(1,1)到(i,j)的路径数量是从(1,1)到(i-1,j)的路径数量即dp[i-1][j]和从(1,1)到(i,j-1)的路径数量即dp[i][j-1]的和。这是因为只能向右或向下走所以(i,j)只可能从(i-1,j)或(i,j-1)到达。
最后输出dp[n][m]即从(1,1)到(n,m)的路径数量。
注意
如果行号和列数都是偶数不能走入这一格中。 AC代码
#include algorithm
#include iostream
#define mp make_pair
#define AUTHOR HEX9CF
using namespace std;
using ll long long;const int N 1e4 7;
const int INF 0x3f3f3f3f;
const ll MOD 1e9 7;int n, m;
int dp[N][N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n m;dp[1][1] 1;for (int i 2; i n; i) {dp[i][1] 1;}for (int j 2; j m; j) {dp[1][j] 1;}for (int i 2; i n; i) {for (int j 2; j m; j) {if (!((i % 2) || (j % 2))) {// 如果行号和列数都是偶数不能走入这一格中。dp[i][j] 0;continue;}dp[i][j] dp[i - 1][j] dp[i][j - 1];}}cout dp[n][m] \n;return 0;
}
