?

• ?1000ms
• ?131072K

AA?點有一個過河卒，需要走到目標?BB?點。卒行走規則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的?CC?點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。例如上圖?CC?點上的馬可以控制?99?個點（圖中的?P1,P2 \cdots P8P1,P2?P8?和?CC）。卒不能通過對方馬的控制點。

棋盤用坐標表示，AA?點（00，00）、BB?點（nn，mm）、CC?點（c_xcx?，c_ycy?）(0 < c_x < n \leq 200<cx?<n≤20，0 < c_y < m \leq 200<cy?<m≤20)。現在要求你計算出過河卒從?AA?點能夠到達?BB?點的路徑的條數。注：象棋中馬走“日”。

輸入格式

輸入?44?個整數，nn，mm，c_xcx?，c_ycy?，分別表示?BB?點的橫縱坐標和?CC?點的橫縱坐標。

輸出格式

輸出一個整數，代表從?AA?點走到?BB?點的所有路徑數。

樣例輸入

5 5 2 4

樣例輸出

14

代碼如下

?

?

#include<iostream>

?

using namespace std; long long f[31][31]; int dir[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,-1},{2,1},{-2,1},{-2,-1}};int main() {int n,m,cx,cy;cin>>n>>m>>cx>>cy;int d[30][30];for(int i=0;i<30;i++)for(int j=0;j<30;j++)d[i][j]=0;d[cx][cy]=1;for(int k=0;k<8;k++){int tx=cx+dir[k][0];int ty=cy+dir[k][1];if(tx>=0&&tx<=n&&ty<=m&&ty>=0)d[tx][ty]=1;}f[0][0]=1;for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){if(i!=0&&d[i][j]!=1)f[i][j]=f[i][j]+f[i-1][j];if(j!=0&&d[i][j]!=1)f[i][j]=f[i][j]+f[i][j-1];}cout<<f[n][m]<<endl; }

?

?

?

?

?

?

?

?

?

?

?

?

?

?

總結

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

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