郑州网站制作公,哪里有网站设计的公司,武侯区建设局网站,如东网站制作原题链接#xff1a;[蓝桥杯 2020 省 AB1] 走方格 - 洛谷
目录
1.题目描述
2.思路分析
3.代码实现 1.题目描述 2.思路分析
题目大意#xff1a;现在有个人站在第 1 行第 1 列#xff0c;要走到第 i 行第 j 列#xff08;每次只能向右或者向下走#xff09;#xff0…原题链接[蓝桥杯 2020 省 AB1] 走方格 - 洛谷
目录
1.题目描述
2.思路分析
3.代码实现 1.题目描述 2.思路分析
题目大意现在有个人站在第 1 行第 1 列要走到第 i 行第 j 列每次只能向右或者向下走如果行号和列号都是偶数不能走入这一格中。问有多少种方案
dp。
设dp[i][j]表示走到第 i 行第 j 列时的方案数。
初始状态dp[1][j]dp[i][1]0 因为每次只能向右或向下走所以如果从1,1到第一行上所有的点的方案只有水平向右走这一种。从1,1到第一列上所有点的方案只有竖直向下这一种。
状态转移方程: dp[i][j]dp[i-1][j]dp[i][j-1]
因为不能走入行号和列号均为偶数的格子所以当行号和列号均为偶数也就是i%20j%20时dp[i][j]0。
因为我们已经考虑过了从1,1到第一行或者到第一列的情况所以循环枚举时我们从2,2开始。
求解目标dp[n][m]
3.代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
ll dp[40][40];int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m; cin n m;for (int i 1; i n; i) dp[i][1] 1;for (int j 1; j m; j) dp[1][j] 1;for (int i 2; i n; i) {for (int j 2; j m; j) {if (i % 2 0 j % 2 0) dp[i][j] 0;else dp[i][j] dp[i - 1][j] dp[i][j - 1];}}cout dp[n][m] endl;return 0;
}
