思路还是DP，用dp(i,j)表示起点到(i,j)的路径数，用备忘录memo消除重叠子问题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * @author ice
 * @Description: P1002 [NOIP2002 普及组] 过河卒
 * @date 2024/12/12
 */
public class Main {

    // 消除重叠子问题
    long[][] memo;

    private int hX, hY;
    private int destX, destY;
    public static void main(String[] args) throws IOException {
        Main p1002 = input();

        // base case
        p1002.memo = new long[p1002.destX + 1][p1002.destY + 1];
        for (int i = 0; i < p1002.destX + 1; i++) {
            Arrays.fill(p1002.memo[i], -1);
        }
        p1002.memo[0][0] = 1;
        int[][] dir = new int[][]{{1, 2}, {1, -2},{-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        p1002.memo[p1002.hX][p1002.hY] = 0;
        for (int i = 0; i < dir.length; i++) {
            int x = p1002.hX + dir[i][0];
            int y = p1002.hY + dir[i][1];
            if (!p1002.exceedBorder(x, y)) {
                p1002.memo[x][y] = 0;
            }
        }

        // dp
        System.out.println(p1002.dp(p1002.destX, p1002.destY));
        return;
    }

    // dp(i, j)表示从起点到(i, j)的路径数
    private long dp(int i, int j) {
        if (exceedBorder(i, j)) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        return memo[i][j] = dp(i - 1, j) + dp(i, j - 1);
    }

    private boolean exceedBorder(int x, int y) {
        if (x > this.destX || y > this.destY || x < 0 || y < 0) {
            return true;
        }
        return false;
    }

    private static Main input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        Main p1002 = new Main();
        for (int i = 0; i < 2; i++) {
            st.nextToken();
            int x = (int)st.nval;
            st.nextToken();
            int y = (int)st.nval;
            if (i == 0) {
                p1002.destX = x;
                p1002.destY = y;
            } else {
                p1002.hX = x;
                p1002.hY = y;
            }
        }
        return p1002;
    }
}