普及⏱ 1000ms💾 256MB#P5145🏷️ 动态规划递推

题目描述

仓库货架间有一张坐标网,巡检机器人要从 $A$ 口 $(0,0)$ 走到 $B$ 口 $(n,m)$, 每步只能向右或向下。网内有一处漏水点 $C$,漏水点与其"波及格" (马步八向可达格)都不能通行。

求机器人从 $A$ 到 $B$ 的不同巡检线路条数。路线可能很多,用 64 位整数计数。 坐标满足 $C \ne A$ 且 $C \ne B$。

输入格式

一行,四个整数 $n, m$ 与漏水点坐标 $C_x, C_y$,用空格分开。

输出格式

一行,一个整数:可通行的巡检线路条数。

数据范围

$$0 \le n, m \le 20$$

样例输入 #1
8 6 0 4
样例输出 #1
1617
样例输入 #2
6 6 3 3
样例输出 #2
6