马拦过河卒(NOIP2002)
馬攔過河卒(NOIP2002)
(2010-05-14 15:57:22)標簽： 遞歸雜談 | 分類： 遞歸與回溯 |
如圖，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
?
Sample Output
17
?方法一：用回溯的方法：（分析略，見跳馬）
Code?1//馬攔過河卒(NOIP2002)
?2program?guoheju;
?3const
?4????dx:array[1..8]?of?integer=(-2,-1,1,2,2,1,-1,-2);
?5????dy:array[1..8]?of?integer=(1,2,2,1,-1,-2,-2,-1);?//馬控制的8個
?6
?7方向
?8var
?9????n,m,x,y,i,j,ans:longint;
10????g:array[0..20,0..20]?of?0..1;?//描述棋盤上的點是否受馬控制
11
12procedure?init;
13begin
14????readln(n,m,x,y);
15????g[x,y]:=1;
16????ans:=0;
17????for?i:=1?to?8?do
18????????if(x+dx[i]>=0)and(x+dx[i]<=n)
19????????and(y+dy[i]>=0)and(y+dy[i]<=m)?then
20????????????g[x+dx[i],y+dy[i]]:=1;???//計算存儲馬的控制點
21end;
22
23procedure?try(x,y:integer);?//x,y為卒當前所在的位置
24begin
25????if(x=n)and(y=m)?then?ans:=ans+1??//到達目標
26????else
27????begin
28????????if(y<m)and(g[x,y+1]=0)?then?try(x,y+1);?//向右走
29????????if(x<n)and(g[x+1,y]=0)?then?try(x+1,y);?//向下走
30????end;
31end;
32
33begin
34????init;
35????try(0,0);
36????writeln(ans);
37end.
?
方法二：用遞推的方法：
??????當m,n比較小的時候，運用回溯可以求出解，但當m、n比較大的時候，就會超時。
??????仔細觀察，要到達棋盤上的任意一點，只能從左邊和上邊兩個方向過來。因此，要到達某一點的路徑數，等于和它相鄰的左、上兩個點的路徑數和：F[i,j] = F[i-1,j] + F[i,j-1]。所以我們可以使用逐列（或逐行）遞推的方法來求出從起始頂點到重點的路徑數目，即使有障礙（我們將馬的控制點稱為障礙），這一方法也完全適用，只要將到達該點的路徑數目置為0即可，用F[i,j]表示到達點(i,j)的路徑數目，g[i,j]表示點(i, j)有無障礙，遞推方程如下：
F[0,0] = 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] = 0 { g[x,y] = 1 }? //障礙點
? F[i,j] = F[i-1,j] + F[i,j-1] {i > 0, j > 0, g[x, y] = 0}//遞推式
與動態規劃相比較，本題不是求最優值，在階段中不做決策。
為了輸出路徑數量夠大，采用數據類型為comp
Code?1//馬攔過河卒(NOIP2002)遞推
?2program?guoheju02;
?3const
?4????dx:array[1..8]?of?integer=(-2,-1,1,2,2,1,-1,-2);
?5????dy:array[1..8]?of?integer=(1,2,2,1,-1,-2,-2,-1);
?6var
?7????n,m,x,y,i,j:integer;
?8????g:array[0..20,0..20]?of?integer;
?9????f:array[0..20,0..20]?of?comp;??//數據類型避免使用高精度
10
11procedure?init;
12begin
13????readln(n,m,x,y);
14????fillchar(g,sizeof(g),0);
15????g[x,y]:=1;
16????for?i:=1?to?8?do
17????????if(x+dx[i]>=0)and(x+dx[i]<=n)
18????????and(y+dy[i]>=0)and(y+dy[i]<=m)?then
19????????????g[x+dx[i],y+dy[i]]:=1;
20end;
21
22procedure?main;
23begin
24????f[0,0]:=1;????//起點
25????for?i:=1?to?n?do
26????????if?g[i,0]=0?then?f[i,0]:=f[i-1,0];//左邊界
27????for?j:=1?to?m?do
28????????if?g[0,j]=0?then?f[0,j]:=f[0,j-1];//上邊界
29????for?i:=1?to?n?do
30????????for?j:=1?to?m?do
31????????????if?g[i,j]=0?then
32????????????????f[i,j]:=f[i-1,j]+f[i,j-1];
33end;
34
35begin
36????init;
37????main;
38????writeln(f[n,m]:0:0);//注意輸出格式
39end.
總結
以上是生活随笔為你收集整理的马拦过河卒(NOIP2002)的全部內容，希望文章能夠幫你解決所遇到的問題。
