题解 | [NOIP2002 普及组] 过河卒

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x, y;                 // B(n,m)，马在 (x,y)
    cin >> n >> m >> x >> y;
    vector<vector<char>> ban(n + 1, vector<char>(m + 1, 0));
    auto mark = [&](int r, int c) {
        if (0 <= r && r <= n && 0 <= c && c <= m) ban[r][c] = 1;
    };
    // 马及其8个控制点
    mark(x, y);
    const int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
    const int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
    for (int k = 0; k < 8; ++k) mark(x + dx[k], y + dy[k]);
    vector<long long> dp(m + 1, 0);        // dp[j] 表示当前行到 (i,j) 的走法数
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (ban[i][j]) {
                dp[j] = 0;
                continue;
            }
            if (i == 0 && j == 0) {
                dp[j] = 1;
                continue;
            }
            long long from_up   = (i ? dp[j]     : 0);   // 上一行同列
            long long from_left = (j ? dp[j - 1] : 0);   // 本行前一列
            dp[j] = from_up + from_left;
        }
    }
    cout << dp[m] << '\n';
    return 0;
}