经典问题—过河卒 解决思路（C++）

解题思路：

有如下棋盘：(*代表移动路径，i 代表x1，j 代表y1)

      0 1 2 3 4

      —————

   0 |A 1 1 1 1

   1 |1 1 1 1 1

   2 |1 1 1 1 1

已知卒在A(0,0)处，我们假设B在(1,0)或者(0,1),那么卒的移动路径只有1条 ，如下图：

       0 1 2 3 4           0 1 2 3 4

    —————>j      ————>j

   0 |A 1 1 1 1       0 |A B 1 1 1

   1 |B 1 1 1 1       1 |1 1 1 1 1

   2 |1 1 1 1 1       2 |1 1 1 1 1

     i                         i

   如果我们假设B在(1,1)，那么就有2条路可走 

      0 1 2 3 4             0 1 2 3 4

    —————j         —————j

   0 |A 1 1 1 1        0 |A * 1 1 1

   1 |* B 1 1 1         1 |1 B 1 1 1

   2 |1 1 1 1 1        2 |1 1 1 1 1

     i                          i

如果我们假设B在(2,1)，那么就有3条路可走 

  0 1 2 3 4                     0 1 2 3 4               0 1 2 3 4

        —————j         —————j          —————j

   0 |A 1 1 1 1           0 | A * 1 1 1           0 |A 1 1 1 1

   1 |* 1 1 1 1            1 | 1 * 1 1 1           1 |* *  1 1 1

   2 |* B 1 1 1            2 | 1 B 1 1 1          2 |1 B 1 1 1

    i                               i                            i

   我们可以发现，卒的移动路径数量等于卒的上方路径+左边路径，

       0 1 2 3 4                0 1 2 3 4

      —————j         —————j

   0 |A 1 1 1 1           0 |A 1 1 1 1

   1 |1 2 1 1 1           1 |1 2 1 1 1

   2 |1 1 1 1 1           2 |1 3 1 1 1

     i                              i

       1+1=2                  2+1=3

   于是就有：a[i][j]=a[i-1][j]+a[i][j-1]

   然后根据这个核心方程去处理马的位置以及一些边界条件就ok了 (^_^)

（如果手机端看不了那就换电脑端看）

参考代码：

#includeusing namespace std;

int main(){
	int x1,y1,x2,y2;//B(x1,xy)，C(x2,y2) ，B是终点，C是马的位置 
	int a[25][25];//题目要求是20以内，棋盘没必要弄太大
	cin>>x1>>y1>>x2>>y2;
	//将棋盘初始化为1【A(0,0)到 B(x1,y1)】 
	for(int i=0;i<=x1;++i){
		for(int j=0;j<=y1;++j){
			a[i][j]=1;
		}
	}
	//设置马的位置以及马能跳到的位置。由于太菜了所以只能用最笨方法 
	a[x2][y2]=0;//这里是马的位置，下面是马能跳到的位置 
	//这里要先判断马能跳到的位置是否超出棋盘，如果没超过才能标记为0 
	if(x2+2<=x1&&y2+1<=y1){a[x2+2][y2+1]=0;}//p1
	if(x2+1<=x1&&y2+2<=y1){a[x2+1][y2+2]=0;}//p2
	if(x2-1<=x1&&y2+2<=y1){a[x2-1][y2+2]=0;}//p3
	if(x2-2<=x1&&y2+1<=y1){a[x2-2][y2+1]=0;}//p4
	if(x2-2<=x1&&y2-1<=y1){a[x2-2][y2-1]=0;}//p5
	if(x2-1<=x1&&y2-2<=y1){a[x2-1][y2-2]=0;}//p6
	if(x2+1<=x1&&y2-2<=y1){a[x2+1][y2-2]=0;}//p7
	if(x2+2<=x1&&y2-1<=y1){a[x2+2][y2-1]=0;}//p8
	//下面是状态转移方程 
	for(int i=0;i<=x1;++i){
		for(int j=0;j<=y1;++j){
			
			if(a[i][j]==0){
				continue;
			}else if(i==0&&j==0){
				continue;
			}else if(i==0){
				a[i][j]=a[i][j-1];
			}else if(j==0){
				a[i][j]=a[i-1][j];
			}else {
				a[i][j]=a[i-1][j]+a[i][j-1];

			}
	
		}
	}
	cout<<a[x1][y1]<<endl;
	return 0;
}

如有错误，欢迎指出！