`
lilisalo
  • 浏览: 1102010 次
文章分类
社区版块
存档分类
最新评论

马拦过河卒(NOIP2002)

 
阅读更多

马拦过河卒(NOIP2002)

(2010-05-14 15:57:22)
标签:

递归

杂谈

分类: 递归与回
Description :

如图,A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。

同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为方马的控制点。例如上图C点上的马可以控制9个点(图中的P1,P2...P8和C)。卒不能通过对方的控制点。
棋盘用坐标表示,A点(0,0)、B点(n, m)(n,m为不超过20的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定:C≠A,同时C≠B)。现在要求你计算出卒从A点能够到达B点的路 径的条数。

Input

B点的坐标(n,m)以及对方马的坐标(X,Y) {不用判错}

Output

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

Sample Input
6 6 3 2

<wbr></wbr>

Sample Output
17

<wbr>方法一:用回溯的方法:(分析略,见跳马)</wbr>

马拦过河卒(NOIP2002)马拦过河卒(NOIP2002)Code
<wbr>1</wbr>//马拦过河卒(NOIP2002)
<wbr>2</wbr>program<wbr>guoheju;<br></wbr><wbr>3</wbr>const
<wbr>4</wbr><wbr><wbr><wbr><wbr>dx:</wbr></wbr></wbr></wbr>array[1..8]<wbr></wbr>of<wbr>integer</wbr>=(-2,-1,1,2,2,1,-1,-2);
<wbr>5</wbr><wbr><wbr><wbr><wbr>dy:</wbr></wbr></wbr></wbr>array[1..8]<wbr></wbr>of<wbr>integer</wbr>=(1,2,2,1,-1,-2,-2,-1);<wbr></wbr>//马控制的8个
<wbr>6</wbr>
<wbr>7</wbr>方向
<wbr>8</wbr>var
<wbr>9</wbr><wbr><wbr><wbr><wbr>n,m,x,y,i,j,ans:longint;<br></wbr></wbr></wbr></wbr>10<wbr><wbr><wbr><wbr>g:</wbr></wbr></wbr></wbr>array[0..20,0..20]<wbr></wbr>of<wbr></wbr>0..1;<wbr></wbr>//描述棋盘上的点是否受马控制
11
12procedure<wbr>init;<br></wbr>13begin
14<wbr><wbr><wbr><wbr>readln(n,m,x,y);<br></wbr></wbr></wbr></wbr>15<wbr><wbr><wbr><wbr>g[x,y]:</wbr></wbr></wbr></wbr>=1;
16<wbr><wbr><wbr><wbr>ans:</wbr></wbr></wbr></wbr>=0;
17<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>for<wbr>i:</wbr>=1<wbr></wbr>to<wbr></wbr>8<wbr></wbr>do
18<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(x+dx[i]>=0)and(x+dx[i]<=n)
19<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>and(y+dy[i]>=0)and(y+dy[i]<=m)<wbr></wbr>then
20<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>g[x</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>+dx[i],y+dy[i]]:=1;<wbr><wbr><wbr></wbr></wbr></wbr>//计算存储马的控制点
21end;
22
23procedure<wbr>try(x,y:integer);<wbr></wbr></wbr>//x,y为卒当前所在的位置
24begin
25<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>if(x=n)and(y=m)<wbr></wbr>then<wbr>ans:</wbr>=ans+1<wbr><wbr></wbr></wbr>//到达目标
26<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>else
27<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>begin
28<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(y<m)and(g[x,y+1]=0)<wbr></wbr>then<wbr>try(x,y</wbr>+1);<wbr></wbr>//向右走
29<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(x<n)and(g[x+1,y]=0)<wbr></wbr>then<wbr>try(x</wbr>+1,y);<wbr></wbr>//向下走
30<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>end;
31end;
32
33begin
34<wbr><wbr><wbr><wbr>init;<br></wbr></wbr></wbr></wbr>35<wbr><wbr><wbr><wbr>try(</wbr></wbr></wbr></wbr>0,0);
36<wbr><wbr><wbr><wbr>writeln(ans);<br></wbr></wbr></wbr></wbr>37end.

<wbr></wbr>

方法二:用递推的方法:
<wbr><wbr><wbr><wbr><wbr><wbr>当m,n比较小的时候,运用回溯可以求出解,但当m、n比较大的时候,就会超时。<br><wbr><wbr><wbr><wbr><wbr><wbr>仔细观察,要到达棋盘上的任意一点,只能从左边和上边两个方向过来。因此,要到达某一点的路径数,等于和它相邻的左、上两个点的路径数和:F[i,j] = F[i-1,j] + F[i,j-1]。所以我们可以使用逐列(或逐行)递推的方法来求出从起始顶点到重点的路径数目,即使有障碍(我们将马的控制点称为障碍),这一方法也完全适用,只要将到达该点的路径数目置为0即可,用F[i,j]表示到达点(i,j)的路径数目,g[i,j]表示点(i, j)有无障碍,递推方程如下:<br>         F[0,0] = 1<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>//起点<br>         F[i,0] = F[i-1,0]        {i &gt; 0, g[x,y] = 0}//左边界<br>         F[0,j] = F[0,j-1]        {j &gt; 0, g[x,y] = 0}//上边界<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>F[i,j] = 0            { g[x,y] = 1 }<wbr> //障碍点<br><wbr>        F[i,j] = F[i-1,j] + F[i,j-1]  {i &gt; 0, j &gt; 0, g[x, y] = 0}//递推式</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

与动态规划相比较,本题不是求最优值,在阶段中不做决策。

为了输出路径数量够大,采用数据类型为comp

马拦过河卒(NOIP2002)马拦过河卒(NOIP2002)Code
<wbr>1</wbr>//马拦过河卒(NOIP2002)递推
<wbr>2</wbr>program<wbr>guoheju02;<br></wbr><wbr>3</wbr>const
<wbr>4</wbr><wbr><wbr><wbr><wbr>dx:</wbr></wbr></wbr></wbr>array[1..8]<wbr></wbr>of<wbr>integer</wbr>=(-2,-1,1,2,2,1,-1,-2);
<wbr>5</wbr><wbr><wbr><wbr><wbr>dy:</wbr></wbr></wbr></wbr>array[1..8]<wbr></wbr>of<wbr>integer</wbr>=(1,2,2,1,-1,-2,-2,-1);
<wbr>6</wbr>var
<wbr>7</wbr><wbr><wbr><wbr><wbr>n,m,x,y,i,j:integer;<br></wbr></wbr></wbr></wbr><wbr>8</wbr><wbr><wbr><wbr><wbr>g:</wbr></wbr></wbr></wbr>array[0..20,0..20]<wbr></wbr>of<wbr>integer;<br></wbr><wbr>9</wbr><wbr><wbr><wbr><wbr>f:</wbr></wbr></wbr></wbr>array[0..20,0..20]<wbr></wbr>of<wbr>comp;<wbr><wbr></wbr></wbr></wbr>//数据类型避免使用高精度
10
11procedure<wbr>init;<br></wbr>12begin
13<wbr><wbr><wbr><wbr>readln(n,m,x,y);<br></wbr></wbr></wbr></wbr>14<wbr><wbr><wbr><wbr>fillchar(g,sizeof(g),</wbr></wbr></wbr></wbr>0);
15<wbr><wbr><wbr><wbr>g[x,y]:</wbr></wbr></wbr></wbr>=1;
16<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>for<wbr>i:</wbr>=1<wbr></wbr>to<wbr></wbr>8<wbr></wbr>do
17<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(x+dx[i]>=0)and(x+dx[i]<=n)
18<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>and(y+dy[i]>=0)and(y+dy[i]<=m)<wbr></wbr>then
19<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>g[x</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>+dx[i],y+dy[i]]:=1;
20end;
21
22procedure<wbr>main;<br></wbr>23begin
24<wbr><wbr><wbr><wbr>f[</wbr></wbr></wbr></wbr>0,0]:=1;<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>//起点
25<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>for<wbr>i:</wbr>=1<wbr></wbr>to<wbr>n<wbr></wbr></wbr>do
26<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if<wbr>g[i,</wbr>0]=0<wbr></wbr>then<wbr>f[i,</wbr>0]:=f[i-1,0];//左边界
27<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>for<wbr>j:</wbr>=1<wbr></wbr>to<wbr>m<wbr></wbr></wbr>do
28<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if<wbr>g[</wbr>0,j]=0<wbr></wbr>then<wbr>f[</wbr>0,j]:=f[0,j-1];//上边界
29<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>for<wbr>i:</wbr>=1<wbr></wbr>to<wbr>n<wbr></wbr></wbr>do
30<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>for<wbr>j:</wbr>=1<wbr></wbr>to<wbr>m<wbr></wbr></wbr>do
31<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if<wbr>g[i,j]</wbr>=0<wbr></wbr>then
32<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>f[i,j]:</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>=f[i-1,j]+f[i,j-1];
33end;
34
35begin
36<wbr><wbr><wbr><wbr>init;<br></wbr></wbr></wbr></wbr>37<wbr><wbr><wbr><wbr>main;<br></wbr></wbr></wbr></wbr>38<wbr><wbr><wbr><wbr>writeln(f[n,m]:</wbr></wbr></wbr></wbr>0:0);//注意输出格式
39end.
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics