haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

过河卒

发布时间:2013-12-18 11:35:59  

过河卒

问题描述

:

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

输入:

B点的坐标(n,m)以及对方马的坐标(X,Y)

输出:

一个整数(路径的条数)。

输入输出样例:

输入:6 6 3 2 输出:17

参考程序1:(动态规划)

{$n+}

const

move:array[1..8,1..2] of integer=((1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)); {增量} var

n, m, x, y, i, j,k:integer;

list:array[-1..20,-1..20] of comp;{路径数序列,其中list[I,j]为卒从(0,0)到(I,j)的路径数}

can:array[0..20,0..20] of boolean; {点(I,j)允许卒通行的标志}

begin

readln(n, m,x,y);

fillchar(can, sizeof(can), true);

can[x,y]:=false; {对方马所在的点为控制点}

for i:=1 to 8 do begin {从(x,y)出发,沿8个跳马方向计算控制点}

j:=x+move[i,1];{计算I方向的跳马位置(j,k)}

k:=y+move[i,2];

if (j>=0)and(k>=0)and(j<=n)and(k<=m)

then can[j,k]:=false;{ 若(j,k)在界内,则为控制点}

end;

if (not can[0,0])or(not can[n,m])

then writeln(0) {若卒的起点和终点为控制点,则输出路径数0}

else begin {动态规划}

fillchar(list, sizeof(list), 0); {路径数序列初始化}

list[0,0]:=1; {卒从(0,0)出发的路径数为1,这个位置不再允许卒通行} can[0,0]:=false;

for i:=0 to n do

for j:=0 to m do {对于每个可行点,卒要么从左侧,要么从上方走到,由此

计算从(0,0)到(I,j)的路径数}

if can[i,j] then list[i,j]:=list[i-1,j]+list[i,j-1];

writeln(list[n,m]:15:0); {输出卒从(0,0)走到(n,m)的路径条数list[n,m]} end;

end.

参考程序2:(回溯法)

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: byte; { n,m为棋盘终点位置 }

g:array[0..20,0..20] of 0..1; {描述棋盘上的点是否受马控制}

c:longint; {存放总路径数}

procedure sol (x,y:integer); { x,y为当前马所在的位置}

var i:integer;

begin

if (x=n) and (y=m) then begin

c:=c+1; {如果已达终点,则总路径数加1}

exit; {回溯}

end;

if (y<m) and (g[x,y+1]=0) then sol (x,y+1); {可以向右走,则向右}

if (x<n) and (g[x+1,y]=0) then sol (x+1,y); {可以向下走,则向下}

end;

begin

readln(n,m,x,y);

g[x,y] := 1;

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]]:=1; {计算马的控制点}

sol(0,0);

writeln(c);

end.

测试数据:

上一篇:均分纸牌
下一篇:方陈填数
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com