马拦过河卒
Time Limit: 3000MS Memory limit: 65536K
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点（0，0）、B点（n，m）（n，m为不超过15的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入
一行四个数据，用空格分隔，分别表示B点的坐标和马的坐标。
输出
一个数据，表示所有的路径条数。
示例输入
6 6 3 3
示例输出
6
1 #include<stdio.h>
2 int main ()
3 {
4 int tx[]={
0,-
2,-
1,
1,
2,
2,
1,-
1,-
2};
5 int ty[]={
0,
1,
2,
2,
1,-
1,-
2,-
2,-
1};
6 int n,m,x,y,i,j;
7 int flag[
20][
20]={
0},tag[
20][
20]={
0};
8 scanf(
"%d %d %d %d",&n,&m,&x,&
y);
9 tag[x][y]=
1;//标记是否是马的控制点。
10 for(i=
0;i<=
8;i++
)
11 {
12 if((x+tx[i]>=
0)&&(x+tx[i])<=n&&(y+ty[i]>=
0)&&(y+ty[i])<=
m)
13 tag[x+tx[i]][y+ty[i]]=
1;
14 }
15 for(i=
1;i<=n;i++
)
16 {
17
18 if(tag[i][
0]!=
1) flag[i][
0]=
1;
19 else
20 {
21 for(;i<=n;i++
)
22 flag[i][
0]=
0;
23 }
24 }
25 for(j=
1;j<=m;j++
)
26 {
27 if(tag[
0][j]!=
1) flag[
0][j]=
1;
28 else
29 {
30 for(;j<=m;j++
)
31 flag[
0][j]=
0;
32 }
33 }
34 for(i=
1;i<=n;i++
)
35 for(j=
1;j<=m;j++
)
36 {
37 if(tag[i][j]==
1) flag[i][j]=
0;
38 else flag[i][j]=flag[i-
1][j]+flag[i][j-
1];
39 }
40 printf(
"%d\n",flag[n][m]);
41 return 0;
42 }
f[i][j]表示到达(i,j)的路径数目。
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/02/2996564.html
