【題目描述】

棋盤上A點有一個過河卒，需要走到目標B點。卒行走的規則：可以向下、或者向右。同時在棋盤上的某一點有一個對方的馬（如C點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，如圖3-1中的C點和P1，……，P8，卒不能通過對方馬的控制點。棋盤用坐標表示，A點(0,0)、B點(n, m) (n,m為不超過20的整數),同樣馬的位置坐標是需要給出的，C≠A且C≠B。現在要求你計算出卒從A點能夠到達B點的路徑的條數。

【輸入】

給出n、m和C點的坐標。

【輸出】

從A點能夠到達B點的路徑的條數。

【輸入樣例】

8 6 0 4

【輸出樣例】

1617



例題不怎么詳的解：

過河卒，中國象棋用語，過了河的卒可以向前、向左、向右移動，但是單單不能后退的，所以被廣泛用來形容‘沒有退路’。

也指的一種只能前進不能后退的破釜沉舟的勇氣，或者是指做事小心謹慎步步為營的一種人生態度。

分析：本題中，卒只能向下和右移動，而不能往回走或往左走。可以很快看出，本題可以用搜索來做。但是根據書上來說，好像無法承受較大的數據規模。 以后學完動態規劃來把動規算法補上。 用遞推的方法，我們可以用一個數組儲存到某一點的路徑總數，另一個數組（bool型）儲存整張棋盤，來代表某個位置馬是否能夠到達。 假設用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}； 根據題目，可以看出卒要從左上到右下，那么只能以向下走和向右走的方法到達終點。換句話說，以逆推的思想，棋盤上的每一個點只能從這個點的左邊或者上邊到達，由此判斷，如果在棋盤上面和左邊的邊緣上有馬可以達到的位置，那么從這個點往后的剩下的整行或整列，卒都不能到達。 而且，從題目來看，這個卒的行走路徑還具有很強的不可逆性，無法回頭，很容易注意到，棋子每向右走一步，那么它上一步所在的位置的整列（colum）都將無法到達，得出遞推關系式： F[0,J]=F[0,J-1]{J>0,G[0,J]=0}； 同理，棋子每向下走一步，那么踏上一步所在位置的整行（row）都將無法到達，則有遞推關系式： F[I,0]=F[I-1,0]{I>0,G[I,0]=0}； 這兩個關系式都可以看作是用來排除不可能條件的，對真正得出答案沒用，缺少了一個核心遞推式。 要讓程序進行下去，最關鍵的關系式： F[I,J]=F[I-1,J]+F[I,J-1]{I>0,J>0,G[I,J]=0}； 這里很容易看明白，[i-1][j-1]代表的就是目前點[i,j]左邊的點和上面的點總共的可到達路徑條數，很明顯，其總和就是該點的有效路徑。 從一開始的很容易看出來的遞推邊界開始遞推：
F[0,0]=1； 即可得出答案。（哎，第一篇寫的就這么麻煩，不過挺清楚的。） 樣例代碼如下： #include<iostream> #include<cstring> using namespace std; long long a[30][30]; int vis[30][30]; int next[][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}}; int main() {int n,m;int x,y;int nx,ny;int i,j;memset(vis,0,sizeof(vis));cin>>n>>m>>x>>y;a[0][0]=0;//處理A=B的情況vis[x][y]=1;//設置馬管轄的位置 a[x][y]=0;for(i=0;i<8;i++){nx=x+next[i][0];ny=y+next[i][1];if(0<=nx&&nx<=n&&0<=ny&&ny<=m){vis[nx][ny]=1;a[nx][ny]=0;}}for(i=0;i<=n;i++){if(vis[i][0]==1)while(i<=n){i++;a[i][0]=0;}else a[i][0]=1;}for(j=0;j<=m;j++){if(vis[0][j]==1)while(j<=m){j++;a[0][j]=0;}else a[0][j]=1;}for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(vis[i][j]==0)a[i][j]=a[i][j-1]+a[i-1][j];cout<<a[n][m]<<endl;return 0; }

?

2019-01-28 11:51:23 轉載請聯系作者

轉載于:https://www.cnblogs.com/DarkValkyrie/p/10329614.html

總結

以上是生活随笔為你收集整理的过河卒(Noip2002)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。