作业帮过河卒救急棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则：可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.棋盘
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/13 14:18:50
过河卒救急棋盘上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位的样子).