2085. Avoid Roads

单点时限: 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 奖励。

创建: 11 年,11 月前.

修改: 2 年,5 月前.

最后提交: 9 年,3 月前.

来源: TC

题目标签