0 人解决，7 人已尝试。
0 份提交通过，共有 13 份提交。
9.9 EMB 奖励。
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 */
题目标签