P1002 [NOIP2002 普及组] 过河卒
基础DP
卒只能向右/向下
由此可得转移方程
dp[i][j] = dp[i -1][j] + dp[i][j - 1]
卒不能走马能到的地方和马所在的地方
则用一个数组标记马能到的地方和马所在的地方，在经过该点的时候跳过即可
注意判断边界问题以及dp数组的初始化
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n"
typedef pair<int, int> PII;
const int N = 40;
int fx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int fy[] = {1, 2, 2, 1, -1, -2, -2, -1};
// 马能走到的位置
int dp[N][N];
// dp数组
bool s[N][N];
// 标记
int bx, by, mx, my;
void solve()
{
cin >> bx >> by >> mx >> my;
s[mx][my] = true; // 马在的地方不能走
for (int i = 0; i < 8; i++) {
if (mx + fx[i] >= 0 && my + fy[i] >= 0) s[mx + fx[i]][my + fy[i]] = true;
}
// 这里判断边界，可能出现0 - 2这种情况，数组会越界
if (!s[1][0]) dp[1][0] = 1;
if (!s[0][1]) dp[0][1] = 1;
// 不赋初值则dp[i][j]始终为0，还需判断第一次向右/向下能不能走，能走再赋初值（这两个点可能不能走）
for (int i = 0; i <= bx; i++) {
for (int j = 0; j <= by; j++) {
if (s[i][j]) continue; // 标记有马，不能走
if (i - 1 >= 0 && j - 1 < 0 && dp[i - 1][j]) dp[i][j] = dp[i - 1][j];
else if (i - 1 < 0 && j - 1 >= 0 && dp[i][j - 1]) dp[i][j] = dp[i][j - 1];
else if (i - 1 >= 0 && j - 1 >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
// 判断边界，防止数组越界
// 关于判断数组非空，因为前面赋初值的地方可能为0，然后就导致dp[1][1]为0，就寄了
// 望指正
}
}
cout << dp[bx][by] << endl;
}
signed main()
{
ios;
int T = 1;
//cin >> T;
while(T--)
{
solve();
}
return 0;
}