過河卒（NOIp2002）
【問題描述】
棋盤上A點有一個過河卒，需要走到目標B點。卒行走的規則：可以向下、或者向右。同時在棋盤上C點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。
棋盤用坐標表示，A點(0, 0)、B點(n, m)，(n, m為不超過20的整數)，同樣馬的位置坐標是需要給出的。C≠A且C≠B。現在要求你計算出卒從A點能夠到達B點的路徑的條數，假設馬的位置是固定不動的，並不是卒走一步馬走一步。
基本介紹
- 中文名：過河卒
- 外文名：soldier
- 經典題目：過河卒（跳馬）
算法分析,樣例程式,
算法分析
跳馬是一道老得不能再老的題目，每位編程者都學過，一般是在學習回溯或搜尋算法時，很多書上也有類似的題目，一些比賽中也經常出現這一問題的變形（如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代碼測試圖片