过河卒

题目背景

棋盘上 $A$ 点 $(0, 0)$ 有一个过河卒，需要走到目标 $B$ 点 $(n, m)$。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的。

输入格式

一行四个正整数 $n, m, x, y$，分别表示 $B$ 点坐标 $(n, m)$ 和马的坐标 $(x, y)$。

输出格式

一个整数，表示所有的路径条数。

样例 #1

输入

6 6 3 3

输出

6

样例 #2

输入

8 6 0 4

输出

1617

提示

• 对于 $100\%$ 的数据，$1 \le n, m \le 20$，$0 \le x, y \le 20$
• 保证起点 $(0, 0)$ 不是马的控制点
• 结果可能很大，请使用 long long 类型

递推思路

这是课堂所讲"网格路径"的升级版——多了一个"马"作为障碍物。

设 $dp[i][j]$ 表示从 $(0,0)$ 走到 $(i,j)$ 的路径数。

马的 9 个控制点（马在 $(x, y)$）：

$(x,y), (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1),$ $(x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2)$

这些点在棋盘内的，卒都不能走。

递推公式：若 $(i,j)$ 不是控制点，则

初始条件：$dp[0][0] = 1$

求解目标：$dp[n][m]$

【题目来源】 NOIP 2002 普及组第四题