题四： 过河卒

[问题描述]：

　　棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。
　　同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
　　棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数。

[问题分析]：

　　这是一道老得不能再老的题目了，很多书上都有类似的题目，NOIp97普及组的最后一题就和本题几乎一模一样。有些同学由于没见过与之类似的题目，在比赛时用了搜索，当n到14，15左右就会超时，其实，本题稍加分析，就能发现：要到达棋盘上的一个点，只能从左边过来或是从上面下来，所以根据加法原理，到达某一点的路径数目，等于到达其相邻上，左两点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起始顶点到重点的路径数目，即使有障碍（我们将马的控制点称为障碍），这一方法也完全适用，只要将到达该点的路径数目置为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位的样子)。

[参考程序]

　　下载

总结:

　　四道题目其实都很容易,要想到正确可行的方法并不难,考察的是大家的编程基础,一些基本算法的简单应用,并不需要什么优化技巧,关键是看大家对这些基本算法是否已熟练掌握,只有熟练掌握这些算法,在考试中才能在较短的时间内做好每道题,我们一定要重视基础!


相关链接:NOIp2002普及组解题报告（一）
　　　　　NOIp2002普及组解题报告（二）
　　　　　NOIp2002普及组解题报告（三）
　　　　　NOIp2002普及组解题报告（四）