解题思路:
用dp思路逆推,观察终点到终点的路线一定由上一个点和左边个点而来,故该点的路径数就是上面那个点和左边那个点的路径数和,使用一个二维数组dp[i][j]来存储起点到( i , j )点的路径数,前面这个推论就可以表达成:dp[i][j] = dp[i-1][j] + dp[i][j-1]
然后在这之中还要考虑马拦截的坐标,继续按上面那个思路,假设现在有一个点上方是拦截点,左边是正常的,那么到这个点的方法就只能是从左边而来,即
dp[i][j] = dp[i][j-1],但我们只要将所有dp[i][j]初始化为0,依然可以用dp[i][j] = dp[i-1][j] + dp[i][j-1],即将拦截点的路径数计为0。
注意事项:
题目中说的是棋盘,且含有0,0,故此题中for遍历需要遍历到n,m,因为棋盘其实就可以看作是一个二维数组,而输入的数据就直接是二维数组的下标,不需要再进行减一操作
还有就是注意边界
参考代码:
#include<iostream> using namespace std; int n, m; long dp[30][30];//将说有点初始化为0 int map[30][30]; int dx[8] = { -2,-1,1,2,2,1,-1,-2 }; int dy[8] = { -1,-2,-2,-1,1,2,2,1 }; void Set(int x, int y)//初始化马拦截点 { map[x][y] = 1; for (int i = 0; i < 8; ++i) if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] <= n && y + dy[i] <= m) map[x + dx[i]][y + dy[i]] = 1; } int main() { int horsex, horsey; cin >> n >> m >> horsex >> horsey; Set(horsex, horsey); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= m; ++j) { if (map[i][j] == 1)//只有该点是正常点才进行路径计算 continue; if (i == 0 && j == 0)//起点初始化,到起点的路径为1 dp[i][j] = 1; else if (i == 0 && j != 0)//第一行单独列出计算 dp[i][j] = dp[i][j - 1]; else if (i != 0 && j == 0)//第一列单独列出计算 dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//递推公式 } } cout << dp[n][m]; return 0; }
0.0分
33 人评分
点我有惊喜!你懂得!浏览:1514 |
钟神赛车 (C++代码)浏览:864 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:629 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:538 |
C语言程序设计教程(第三版)课后习题6.3 (C++代码)浏览:949 |
【计算直线的交点数】 (C语言代码)浏览:1442 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:536 |
蛇行矩阵 (C语言代码)浏览:524 |
打印十字图 (C语言代码)浏览:2701 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:484 |