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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N = 21;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int x = in.nextInt();
		int y = in.nextInt();
	  // 使用long，不然最后一个测试案例结果会溢出
		long[][] dp = new long[N][N];
		boolean[][] flag = new boolean[N][N];
	  // 处理了不能访问的点
		flag[x][y] = true;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j <N; j++) {
				if(i == x || j == y)continue;
				if(Math.abs(i-x)+Math.abs(j-y) == 3)flag[i][j]=true;
			}
		}
	  // 处理第一行、第一列，在不能访问的点后面的点都是到达不了的
		for(int j = 0; j <N; j++) {
			if(flag[0][j]) {
				break;
			}
			dp[0][j] = 1;
		}
		for(int i = 0; i <N; i++) {
			if(flag[i][0]) {
				break;
			}
			dp[i][0] = 1;
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
			  // 累加前一步的方案数
				if(!flag[i-1][j])dp[i][j] += dp[i-1][j];
				if(!flag[i][j-1])dp[i][j] += dp[i][j-1];
			}
		}
		System.out.println(dp[n][m]);
	}
}

二维dp+判断能否到达