題目描述
棋盤上A點有一個過河卒,需要走到目標B點。卒行走的規則:可以向下、或者向右。同時在棋盤上C點有一個對方的馬,該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。
棋盤用座標表示,A點(0, 0)、B點(n, m)(n, m為不超過20的整數),同樣馬的位置座標是需要給出的。
現在要求你計算出卒從A點能夠到達B點的路徑的條數,假設馬的位置是固定不動的,並不是卒走一步馬走一步。
輸入輸出格式
輸入格式:
一行四個資料,分別表示B點座標和馬的座標。
輸出格式:
一個數據,表示所有的路徑條數。
輸入輸出樣例
輸入樣例#1:6 6 3 3
輸出樣例#1:6
說明
結果可能很大!
方法/步驟
#include
#include
int a[30][30];
long long f[30][30];
void draw(int x,int y){
int i,j,k;
if(x<0 x>20 y<0 y>20)
return;
else a[x][y]=1;
}
int main(){
int i,j,k,m,n,x,y;
scanf("%d%d%d%d",&m,&n,&x,&y);
draw(x,y);
draw(x+1,y+2);
draw(x+2,y+1);
draw(x+2,y-1);
draw(x+1,y-2);
draw(x-1,y-2);
draw(x-2,y-1);
draw(x-2,y+1);
draw(x-1,y+2);
for(i=1;i<=n;i++)
if(a[0][i]!=1)f[0][i]=1;
else break;
for(i=1;i<=m;i++)
if(a[i][0]!=1)f[i][0]=1;
else break;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(!a[i][j])
f[i][j]=f[i-1][j]+f[i][j-1];
printf("%I64d\n",f[m][n]);
return 0;
}