Time Limit: 10 second
Memory Limit: 2 MB
问题描述
如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。
同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为方马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2...P8和C）。卒不能通过对方的控制点。
棋盘用坐标表示，A点（0，0）、B点（n, m）(n,m为不超过20的整数，并由键盘输入)，同样马 的位置坐标是需要给出的（约定：C≠A，同时C≠B）。现在要求你计算出卒从A点能够到达B点的路 径的条数。
Input
B点的坐标（n,m）以及对方马的坐标（X,Y） {不用判错}
Output
一个整数（路径的条数）。
Sample Input
8 6 0 4
Sample Output
1617
【题解】
这是个递推题，每个卒只能从左上和右上角到达。
设a[i][j]表示卒到达(i,j)这个点的方案数，a[i][j] = a[i][j-1] + a[i-1][j];
首先用一个二维的bool型数组bo[21][21]来表示各个点是否为马所占据。一开始所有的点都置为true.然后把马所在的位置和马跳一步能到的位置置为false。表示这些点不能放卒。接下来是边界，首先for i = 1;i <= xB;i++ 如果遇到的bo[i][0]==true则这个点a[i][0] = 1，如果为false则直接停止。不再往下置1；上边界也是一样的规律。
然后从（1,1）一直递推到XB,YB就可以了，用普通的int不能完整存下数据，要用double型来存。
【代码】
#include <cstdio>
int xb,yb,xm,ym;
double a[21][21];
bool bo[21][21];
void input_data()
{
scanf("%d %d %d %d",&xb,&yb,&xm,&ym);
for (int i = 0;i <= xb;i++)
for (int j = 0;j <= yb;j++) //一开始 所有的位置都能放
bo[i][j] = true;
for (int i = 0;i <= xb;i++) //到达所有点的方案数，都置为0.
for (int j = 0;j <= yb;j++)
a[i][j] = 0;
int x0,y0; //x0 y0是马能控制的点
bo[xm][ym] = false; //这是马所在的点
x0 = xm -1;y0 = ym-2; //接下来的多行都是用来标记马跳一步能到达的点。
if ( (x0 >= 0) && (y0 >=0))
bo[x0][y0] = false;
x0 = xm -2;y0 = ym -1;
if ( (x0 >= 0) && (y0 >=0))
bo[x0][y0] = false;
x0 = xm -2;y0 = ym+1;
if ( (x0 >= 0) && (y0 <=yb))
bo[x0][y0] = false;
x0 = xm - 1;y0 = ym +2;
if ( (x0 >= 0) && (y0 <=yb))
bo[x0][y0] = false;
x0 = xm +1;y0 = ym +2;
if ( ( x0 <= xb) && (y0 <= yb))
bo[x0][y0] = false;
x0 = xm +2;y0 = ym+1;
if ( (x0 <= xb) && (y0 <= yb))
bo[x0][y0] = false;
x0 = xm+1;y0 = ym-2;
if ( (x0 <= xb) && (y0 >=0))
bo[x0][y0] = false;
x0 = xm +2;y0 = ym-1;
if ( (x0 <= xb) && (y0 >=0))
bo[x0][y0] = false;
}
void get_ans()
{
for (int i = 0;i <= xb;i++) //接下来两个for循环 处理边界问题。
if (bo[i][0])
a[i][0] = 1;
else
break;
for (int i = 0;i <= yb;i++)
if (bo[0][i])
a[0][i] = 1;
else
break;
for (int i = 1;i <= xb;i++) //进行递推
for (int j = 1;j <= yb;j++)
if (bo[i][j])
a[i][j] = a[i-1][j] + a[i][j-1];
}
void output_ans()
{
printf("%0.lf
",a[xb][yb]); //%0.lf用来输出double，且不保留小数。
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}