# P1002 [NOIP 2002 普及组] 过河卒

## 题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

![](https://cdn.luogu.com.cn/upload/image_hosting/ipmwl52i.png)

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

## 输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

## 输出格式

一个整数，表示所有的路径条数。

## 输入输出样例 #1

### 输入 #1

6 6 3 3

### 输出 #1

6

## 说明/提示

对于 $100 \%$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

**【题目来源】**

NOIP 2002 普及组第四题

#include <iostream>
#include <cmath>

using namespace std;		

const int MAX_SIZE = 25;
bool blocked[MAX_SIZE][MAX_SIZE];		//这里是设置二维数组的大小。题里的n<=20，这里设定为25肯定不会出界。

long long dp[MAX_SIZE][MAX_SIZE];		//数据量过大，用long long

int main()
{
int n,m; //B点（终点）坐标
int cx,cy; //马的位置坐标		字面意思

cin >> n >> m >> cx >> cy;  		//输入B点坐标与马的位置坐标
  
int dx[] = {0,-2,-1,1,2,2,1,-1,-2};  //第一个为马的初始坐标，后边为马可能的移动方向
int dy[] = {0,1,2,2,1,-1,-2,-2,-1};  //上边的为x移动方向，底下的为y移动方向，一列对应一次的移动
  
for(int i = 0;i < 9;i++){  		
	int target_x = cx + dx[i];  //将马的相对坐标（后） 加上其的绝对坐标（前） 
	int target_y = cy + dy[i];  //循环九次确保第一个是马的绝对坐标 其余为可能会被马踩到的点
	  
	if(target_x >= 0 && target_x <= n && target_y >= 0 && target_y <= m){	//警钟长鸣 这里每一个都是带等号的 之前没加少了个结果  
		blocked[target_x][target_y] = true;	//将所有可能的没有越界的点都设定为DEAD点，if条件防止越界内存溢出  
	}  
}  
dp[0][0] = 1;  	//只有一个方式可以到达（0.0）的起始点
  
for(int i = 0;i <= n;i++)  
{  
	for(int j = 0;j <=m;j++){		//二维数组，逐个循环  
		if(blocked[i][j]){  
			dp[i][j] = 0;  		//如果判定到DEAD点，则到该点的路径数目为0.
			continue;  				//立刻跳过该点的DP环节。
		}  			//在这里到达[i][j]点需要从[i-1][j]或[i][j-1]这两点来。也就是dp[i][j]=dp[i-1][j]+dp[i][j-1]，这里分别判断。
		if(i > 0){  				//第一行没有它的再上一行，所以i > 0.
			dp[i][j] += dp[i-1][j];  
		}  
		if(j > 0){  
			dp[i][j] += dp[i][j-1];  	//第一列没有它的再上一列，所以j > 0.
		}  
	}  
}  
cout << dp[n][m] << endl;  	//输出到达dp[n][m]点的路径数目。
return 0;  


}