P1002 [NOIP2002 普及组] 过河卒

P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态

题目如下：

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

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

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

输出格式
一个整数，表示所有的路径条数。

输入输出样例

说明/提示
对于100%的数据，1 ≤ n, m ≤ 20，0 ≤ 马的坐标 ≤ 20。

题目来源
NOIP 2002 普及组第四题

思路如下：

题目只有向右和向下移动，我们可以很简单的写出状态方程，但是起点是0，0处理很麻烦，所以我们可以同时+1，对边界判断即可。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
ll dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
ll dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; 
const ll N = 1e3+10;
ll arr[N];
ll dp[N][N]; //第i，j时的方案数 
bool vis[N][N];
int main() 
{
	ll fx,fy,xm,ym;
	cin >> fx >> fy >> xm >> ym;
	fx += 1;
	fy += 1;
	xm += 1;
	ym += 1;
	for(ll k = 0 ; k < 8 ; k++)
	{
		ll tx = xm + dx[k];
		ll ty = ym + dy[k];
		if (tx >= 1 && tx <= N && ty >= 1 && ty <= N) 
        vis[tx][ty] = true;
	}
	vis[xm][ym] = true;
	dp[1][1] = 1; 
	for(ll i = 1 ; i <= fx ; i++)
	{
		for(ll j = 1 ; j <= fy ; j++)
		{
			if(vis[i][j] == false)
			{
				if(i > 1)
				dp[i][j] += dp[i-1][j];
				if(j > 1)
				dp[i][j] += dp[i][j-1];
			}
		}
	}
	cout << dp[fx][fy];
    return 0;
}