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;
}