P1002 [NOIP2002 普及组] 过河卒

题目

原题目链接

题目描述
棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，$A$ 点 $(0,0)$、$B$ 点 $(n,m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 $B$ 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
样例输入 #1
6 6 3 3
样例输出 #1
6
提示
对于 $100\%$ 的数据，$1\le n,m\le 20$，$0\le$ 马的坐标 $\le 20$。

前言

很奇怪为什么网上的代码都那么麻烦。

首先，这原本就是一个小学的奥数题，（我没学过，但是我差不多二三年级时，无意间旁听懂了），小学二三年级的奥数题；逆向思维可以秒解。

思路

既然题目说卒只能向下或向右走；那么不妨逆向思维：卒要么可以从上面走过来、要么可以从左边走过来；

（$(0,0)$点当然是$1$了。）假如已经算好有$x$种走法到上面那个点、有$y$种走法到左边那个点，那么就有$x+y$种走法到当前这个点。

举个例子：先假设没有马，卒从$(0,0)$位置到$(10,10)$位置每个点的走法的数量如下。

1       1       1       1       1       1       1       1       1       1       1
1       2       3       4       5       6       7       8       9       10      11
1       3       6       10      15      21      28      36      45      55      66
1       4       10      20      35      56      84      120     165     220     286
1       5       15      35      70      126     210     330     495     715     1001
1       6       21      56      126     252     462     792     1287    2002    3003
1       7       28      84      210     462     924     1716    3003    5005    8008
1       8       36      120     330     792     1716    3432    6435    11440   19448
1       9       45      165     495     1287    3003    6435    12870   24310   43758
1       10      55      220     715     2002    5005    11440   24310   48620   92378
1       11      66      286     1001    3003    8008    19448   43758   92378   184756

每个点的走法的数量都是到上面和左边两个点的走法的数量的和。

那么有马呢，把卒不能去的几个点提前标注出来就够了，如果碰到了标注过的点，就跳过（那么到这个点的走法的数量自然也就为$0$了）。

再举个例子：卒从$(0,0)$位置到$(10,10)$位置，马在$(5,5)$点上。

1       1       1       1       1       1       1       1       1       1       1
1       2       3       4       5       6       7       8       9       10      11
1       3       6       10      15      21      28      36      45      55      66
1       4       10      20      0       21      0       36      81      136     202
1       5       15      0       0       21      21      0       81      217     419
1       6       21      21      21      0       21      21      102     319     738
1       7       28      0       21      21      42      0       102     421     1159
1       8       36      36      0       21      0       0       102     523     1682
1       9       45      81      81      102     102     102     204     727     2409
1       10      55      136     217     319     421     523     727     1454    3863
1       11      66      202     419     738     1159    1682    2409    3863    7726

代码

0. 框架

   int mian(){
   	
   	return 0;
   }
   

   ---

1. 输入m点的坐标（m_x和m_y）和马的位置h点的坐标（h_x和h_y）

   #include<cstdio>	//scanf()
   int m_x, m_y, h_x, h_y;
   int main(){
   	scanf("%d %d %d %d", &m_x, &m_y, &h_x, &h_y);
   	return 0;
   }
   

   ---

2. 模拟棋盘（定义一个二维数组），并标出马和马能去的位置（卒不能去的位置）

   因为是整形数组，正数用于表示到当前这个点的走法的个数，那么就用-1表示这个点卒不能去。

   注意到，因为到后面数字会很大，所以记得用long long。

   再注意到，$(0,0)$点是卒的初始位置，初始值为1

   再再注意到，马能去的位置有可能在棋盘界外；需要判断一下，防止越界。

   #include<cstdio>	//scanf()
   int m_x, m_y, h_x, h_y, p1=1, p2=2;
   long long a[21][21]={1};
   int main(){
   	scanf("%d %d %d %d", &m_x, &m_y, &h_x, &h_y);
   	a[h_x][h_y]=-1;
   	for(int i=0; i<2; i++){
   		p2=-p2;
   		for(int j=0; j<2; j++){
   			if(h_x+p1<0 || h_x+p1>m_x || h_y+p2<0 || h_y+p2>m_y); 
   			else a[h_x+p1][h_y+p2]=-1;
   			if(h_x+p2<0 || h_x+p2>m_x || h_y+p1<0 || h_y+p1>m_y);
   			else a[h_x+p2][h_y+p1]=-1;
   			p1=-p1;
   		}
   	}
   	return 0;
   }
   

   ---

3. 有序地遍历棋盘，求出到当前的走法的数量。

   同样，要注意遍历时数组越界。

   #include<cstdio>	//scanf()
   int m_x, m_y, h_x, h_y, p1=1, p2=2, t;
   long long a[21][21]={1};
   int main(){
   	scanf("%d %d %d %d", &m_x, &m_y, &h_x, &h_y);
   	a[h_x][h_y]=-1;
   	for(int i=0; i<2; i++){
   		p2=-p2;
   		for(int j=0; j<2; j++){
   			if(h_x+p1<0 || h_x+p1>m_x || h_y+p2<0 || h_y+p2>m_y); 
   			else a[h_x+p1][h_y+p2]=-1;
   			if(h_x+p2<0 || h_x+p2>m_x || h_y+p1<0 || h_y+p1>m_y);
   			else a[h_x+p2][h_y+p1]=-1;
   			p1=-p1;
   		}
   	}
   	for(int x=0; x<=m_x; x++){
   		for(int y=0; y<=m_y; y++){
   			t=0;
   			if(a[x-1][y]==-1 || x-1<0);
   			else t+=a[x-1][y];
   			if(a[x][y-1]==-1 || y-1<0);
   			else t+=a[x][y-1];
   			if(a[x][y]==-1);
   			else a[x][y]+=t;
   		}
   	}
   	return 0;
   }
   

   ---

4. 最后，输出终点m的值即可。

   #include<cstdio>	//scanf(), printf()
   int m_x, m_y, h_x, h_y, p1=1, p2=2, t;
   long long a[21][21]={1};
   int main(){
   	scanf("%d %d %d %d", &m_x, &m_y, &h_x, &h_y);
   	a[h_x][h_y]=-1;
   	for(int i=0; i<2; i++){
   		p2=-p2;
   		for(int j=0; j<2; j++){
   			if(h_x+p1<0 || h_x+p1>m_x || h_y+p2<0 || h_y+p2>m_y); 
   			else a[h_x+p1][h_y+p2]=-1;
   			if(h_x+p2<0 || h_x+p2>m_x || h_y+p1<0 || h_y+p1>m_y);
   			else a[h_x+p2][h_y+p1]=-1;
   			p1=-p1;
   		}
   	}
   	for(int x=0; x<=m_x; x++){
   		for(int y=0; y<=m_y; y++){
   			t=0;
   			if(a[x-1][y]==-1 || x-1<0);
   			else t+=a[x-1][y];
   			if(a[x][y-1]==-1 || y-1<0);
   			else t+=a[x][y-1];
   			if(a[x][y]==-1);
   			else a[x][y]+=t;
   		}
   	}
   	printf("%lld", a[m_x][m_y]);
   	return 0;
   }
   

   ---

答案

#include<cstdio>
int m_x, m_y, h_x, h_y, p1=1, p2=2, t;
long long a[21][21]={1};
int main(){
	scanf("%d %d %d %d", &m_x, &m_y, &h_x, &h_y);
	a[h_x][h_y]=-1;
	for(int i=0; i<2; i++){
		p2=-p2;
		for(int j=0; j<2; j++){
			if(h_x+p1<0 || h_x+p1>m_x || h_y+p2<0 || h_y+p2>m_y); 
			else a[h_x+p1][h_y+p2]=-1;
			if(h_x+p2<0 || h_x+p2>m_x || h_y+p1<0 || h_y+p1>m_y);
			else a[h_x+p2][h_y+p1]=-1;
			p1=-p1;
		}
	}
	for(int x=0; x<=m_x; x++){
		for(int y=0; y<=m_y; y++){
			t=0;
			if(a[x-1][y]==-1 || x-1<0);
			else t+=a[x-1][y];
			if(a[x][y-1]==-1 || y-1<0);
			else t+=a[x][y-1];
			if(a[x][y]==-1);
			else a[x][y]+=t;
		}
	}
	printf("%lld", a[m_x][m_y]);
	return 0;
}