pascal编程：过河卒题目描述 棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则：可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/24 11:09:54
pascal编程：过河卒题目描述 棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则：可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对
pascal编程：过河卒
题目描述
棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则：可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.因此称之为“马拦过河卒”.
棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过20的整数),同样马的位置坐标是需要给出的. 现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步.
输入格式
一行四个数据,分别表示B点坐标和马的坐标.
输出格式
一个数据,表示所有的路径条数.
样例输入
6 6 3 3
样例输出
6
注释结果可能很大!
pascal编程：过河卒题目描述 棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则：可以向下、或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对
【问题分析】
跳马是一道老得不能再老的题目,每位编程者都学过,一般是在学习回溯或搜索算法时,很多书上也有类似的题目,一些比赛中也经常出现这一问题的变形（如NOIP1997初中组第三题）.有些同学一看到这种类型的题目就去盲目搜索,但事实证明：当n,m=15就会超时.
其实,对本题稍加分析就能发现,到达棋盘上的一个点,只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点）.根据加法原理,到达某一点的路径条数,就等于到达其相邻的上点或左点的路径数目总和.因此我们可以使用逐列（逐行）递推的方法来求出从起点到终点的路径数目.障碍点（马的控制点）也完全适用,只要将到达该点的路径数目设置为0即可.
假设用F[I,J]到达点（I,J）的路径数目用G[I,J]表示点(I,J)是否为对方马的控制点,G[I,J]=0表示不是对放马的控制点,G[I,J]=1表示是对方马的控制点.则,我们可以得到如下的递推关系式：
F[I,J]=0 {G[I,J]=1}
F[I,0]=F[I-1,0] {I>0,G[I,0]=0}
F[0,J]=F[0,J-1] {J>0,G[0,J]=0}
F[I,J]=F[I-1,J]+F[I,J-1] {I>0,J>0,G[I,J]=0}
上述递推式边界是：F[0,0]:=1.考虑到最大情况下：n=20,m=20,路径条数可能会出现超出长整型范围,所以要用int64或comp类型计数或者高精度运算.
【参考程序】
const dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);
var n,m,x,y,i,j:integer;
g:array[0..20,0..20] of boolean;
f:array[0..20,0..20] of int64;
begin
readln(n,m,x,y);
g[x,y]:=true;
for i:=1 to 8 do
if(x+dx[i]>=0)and(x+dx[i]<=n)and(y+dy[i]>=0)and(y+dy[i]<=m)then
g[x+dx[i],y+dy[i]]:=true;
f[0,0]:=1;
for i:=1 to n do
if not(g[i,0]) then
f[i,0]:=f[i-1,0];
for i:=1 to m do
if not(g[0,i]) then
f[0,i]:=f[0,i-1];
for i:=1 to n do
for j:=1 to m do
if not(g[i,j]) then
f[i,j]:=f[i-1,j]+f[i,j-1];
writeln(f[n,m]);
end.