#NOIPJ2002D. [NOIP2002 普及组] 过河卒

    ID: 1615 Type: Default 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>动态规划记忆化搜索2002NOIp 普及组NOIP 普及组NOIP2002 普及组

[NOIP2002 普及组] 过河卒

题目背景

NOIp2002普及组T4

题目描述

如图,棋盘上 AA 点有一个过河卒,需要走到目标 BB 点。卒行走的规则:可以向下、或者向右。

同时在棋盘上任一点有一个对方的马(如上图的 CC 点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 CC 点上的马可以控制 99 个点(图中的 P1,P2,...,P8P1,P2,...,P8CC)。卒不能通过对方马的控制点。

棋盘用坐标表示,AA(0,0)(0, 0)BB(n,m)(n, m),同样马的位置坐标是需要给出的。现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数。

输入格式

BB 点的坐标 (n,m)(n, m) 以及对方马的坐标 (x,y)(x, y)

输出格式

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

样例

样例输入

6 6 3 2

样例输出

17

提示

对于 100%100 \% 的数据,1n,m201 \le n, m \le 2000 \le x, y 20\le 20CA C \ne A, 同时 CBC \ne B