过河卒救急棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.棋盘
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/10 23:04:46
![过河卒救急棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.棋盘](/uploads/image/z/8550389-29-9.jpg?t=%E8%BF%87%E6%B2%B3%E5%8D%92%E6%95%91%E6%80%A5%E6%A3%8B%E7%9B%98%E4%B8%8AA%E7%82%B9%E6%9C%89%E4%B8%80%E4%B8%AA%E8%BF%87%E6%B2%B3%E5%8D%92%2C%E9%9C%80%E8%A6%81%E8%B5%B0%E5%88%B0%E7%9B%AE%E6%A0%87B%E7%82%B9.%E5%8D%92%E8%A1%8C%E8%B5%B0%E7%9A%84%E8%A7%84%E5%88%99%EF%BC%9A%E5%8F%AF%E4%BB%A5%E5%90%91%E4%B8%8B%E3%80%81%E6%88%96%E8%80%85%E5%90%91%E5%8F%B3.%E5%90%8C%E6%97%B6%E5%9C%A8%E6%A3%8B%E7%9B%98%E4%B8%8AC%E7%82%B9%E6%9C%89%E4%B8%80%E4%B8%AA%E5%AF%B9%E6%96%B9%E7%9A%84%E9%A9%AC%2C%E8%AF%A5%E9%A9%AC%E6%89%80%E5%9C%A8%E7%9A%84%E7%82%B9%E5%92%8C%E6%89%80%E6%9C%89%E8%B7%B3%E8%B7%83%E4%B8%80%E6%AD%A5%E5%8F%AF%E8%BE%BE%E7%9A%84%E7%82%B9%E7%A7%B0%E4%B8%BA%E5%AF%B9%E6%96%B9%E9%A9%AC%E7%9A%84%E6%8E%A7%E5%88%B6%E7%82%B9.%E6%A3%8B%E7%9B%98)
过河卒救急棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.棋盘
过河卒救急
棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右.
同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.
棋盘用坐标表示,A点(0,0)、B点(n,m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的.现在要求你计算出卒从A点能够到达B点的路径的条数.
过河卒救急棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.棋盘
本题稍加分析,就能发现:要到达棋盘上的一个点,只能从左边过来或是从上面下来,所以根据加法原理,到达某一点的路径数目,等于到达其相邻上,左两点的路径数目之和,因此我们可以使用逐列(或逐行)递推的方法来求出从起始顶点到重点的路径数目,即使有障碍(我们将马的控制点称为障碍),这一方法也完全适用,只要将到达该点的路径数目置为0即可,用F[i,j]表示到达点(i,j)的路径数目,g[i,j]表示点(i,j)有无障碍,递推方程如下:
F[0,0] = 1
F[i,j] = 0 { g[x,y] = 1 }
F[i,0] = F[i-1,0] {i > 0,g[x,y] = 0}
F[0,j] = F[0,j-1] {j > 0,g[x,y] = 0}
F[i,j] = F[i-1,j] + F[i,j-1] {i > 0,j > 0,g[x,y] = 0}
本题与第三题一样,也要考虑精度问题,当n,m都很大时,可能会超过MaxLongInt,所以要使用Comp类型计数(Comp类型已经足够了,即使n=20,m=20,没有任何障碍的情况下的结果也只有14,5位的样子).