複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/過河卒/19884189
複製
複製成功

過河卒

（編程經典題目（跳馬））

鎖定
過河卒（NOIp2002）
【問題描述】
棋盤上A點有一個過河卒， [1]  需要走到目標B點。卒行走的規則：可以向下、或者向右。在棋盤上C點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。
棋盤用座標表示，A點(0, 0)、B點(n, m)，(n, m為不超過20的整數)，同樣馬的位置座標是需要給出的。C≠A且C≠B。要求你計算出卒從A點能夠到達B點的路徑的條數，假設馬的位置是固定不動的，並不是卒走一步馬走一步。
中文名
過河卒
外文名
soldier
適用領域
編程
經典題目
過河卒（跳馬）

目錄

  1. 1 算法分析
  2. 2 樣例程序

過河卒算法分析

跳馬是一道老得不能再老的題目，每位編程者都學過，一般是在學習回溯或搜索算法時，很多書上也有類似的題目，一些比賽中也經常出現這一問題的變形（如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類型計數或者高精度運算。

過河卒樣例程序

Pascal
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.
過河卒Pascal代碼測試圖片 過河卒Pascal代碼測試圖片
參考資料