[NOIP2002 普及组] 过河卒
题目描述
棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A点(0, 0) B点(n, m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示B点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
样例 #1
样例输入 #1
样例输出 #1
提示
对于100%的数据,1<=n, <=20,0<=马的坐标<=20。
【题目来源】
NOIP 2002 普及组第四题
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<iostream> #include<bits/stdc++.h> using namespace std; long long xb,yb,xh,yh,pand[30][30]={0},f[30][30]={0};
int main() { cin>>xb>>yb>>xh>>yh; xb+=2;yb+=2; xh+=2;yh+=2; for(int i=1;i<=30;i++){ f[2][i]=1; f[i][2]=1; }
pand[xh][yh]=1; pand[xh-2][yh-1]=1; pand[xh-2][yh+1]=1; pand[xh+2][yh-1]=1; pand[xh+2][yh+1]=1; pand[xh-1][yh+2]=1; pand[xh+1][yh+2]=1; pand[xh-1][yh-2]=1; pand[xh+1][yh-2]=1;
f[1][2]=1; for(int i=2;i<=xb;i++){ for(int j=2;j<=yb;j++){ if(pand[i][j]==1){ f[i][j]=0; continue; } f[i][j]=f[i-1][j]+f[i][j-1]; } } cout<<f[xb][yb]/2; return 0; }
|