**0 人解决**，7 人已尝试。

**0 份提交通过**，共有 13 份提交。

**9.9** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **256 MB

In the city, roads are arranged in a grid pattern. Each point on the grid represents a corner where two blocks meet. The points are connected by line segments which represent the various street blocks. Using the cartesian coordinate system, we can assign a pair of integers to each corner as shown below.

-width will be between 1 and 100 inclusive.

-height will be between 1 and 100 inclusive.

-bad will contain between 0 and 50 elements inclusive.

-Each element of bad will contain between 7 and 14 characters inclusive.

-Each element of the bad will be in the format “a b c d” where,

a,b,c,d are integers with no extra leading zeros,

a and c are between 0 and width inclusive,

b and d are between 0 and height inclusive,

and a,b is one block away from c,d.

-The return value will be between 0 and 2^63-1 inclusive.

You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a list of bads describing which blocks are bad. If (quotes for clarity) “a b c d” is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let’s say

width = 6

length = 6

bad = {“0 0 0 1”,”6 6 5 6”}

The picture below shows the grid, with untraversable blocks darkened in black. A sample path has been highlighted in red.

You will output the number of distinct paths that lead to your destination.

Input

6 6 2 0 0 0 1 6 6 5 6 /* 2 2 3 0 0 1 0 1 2 2 2 1 1 2 1 */

Output

252 /* 0 */

**0 人解决**，7 人已尝试。

**0 份提交通过**，共有 13 份提交。

**9.9** EMB 奖励。

题目标签