1314：【例3.6】過河卒(Noip2002)

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 15966 ??? 通過數: 6732

【題目描述】

? ? ? ? 棋盤上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

【分析】

? ? ? ? 看到棋盤，可能首先想到深搜，事實上，這道題用深搜時，當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]=f[i-1][j]+f[i][j-1]? ? // i>0 且 j>0 且 g[i][j]=0；遞推邊界有4個：

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[0][0]=1

考慮到最大情況下，n=20，m=20，路徑條數可能會超過2^31-1，所以要采用高精度。

【參考代碼】

#include <stdio.h> #define MAXM 25 #define MAXN 25? int g[MAXM][MAXN]; ? ? ? ?//訪問數組，表示點(i,j)有無障礙，0無障礙，1有障礙 int dir[8][2]={{-2,-1},{-1,-2},{2,-1},{1,-2},{2,1},{1,2},{-1,2},{-2,1}}; //方向數組? long long f[MAXM][MAXN]; ? ?//棋盤數組，到達點(i,j)的路徑數目?int n,m; ? ?//棋盤大小 int x,y; ? ?//馬的坐標int main() {int i,j,nx,ny;scanf("%d%d%d%d",&n,&m,&x,&y);//處理馬控制的點g[x][y]=1; ? ? ? //x,y不能走f[0][0]=1;?for(i=0;i<8;i++){nx=x+dir[i][0];ny=y+dir[i][1];if(nx>=0 && nx<=n && ny>=0 && ny<=m)g[nx][ny]=1; ?//不能走?}for(i=1;i<=n;i++){?if(g[i][0])break;elsef[i][0]=1;}?for(i=1;i<=m;i++){if(g[0][i])break;elsef[0][i]=1;}for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(g[i][j]==0)f[i][j]=f[i-1][j]+f[i][j-1];printf("%lld\n",f[n][m]);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1314

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1314：【例3.6】过河卒(Noip2002)）的全部內容，希望文章能夠幫你解決所遇到的問題。

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