ManhattanConstruction | Topcoder Archive

Problem Statement

The term "Manhattan Distance" refers to the distance between two points, calculated as the sum of the absolute differences of their Cartesian coordinates, Abs(x2 - x1) + Abs(y2 - y1). It is so named, because it describes the type of movement that would be made along the grid-like streets of a large city, where all movements happen in fixed increments in vertical or horizontal direction.

Someone beginning at point (0,0), and wanting to travel to point (16, 16), could do so by travelling 16 blocks north then 16 blocks east. Alternately, they could travel 16 blocks east, then 16 blocks north. Another option, they could alternately travel one block north followed by one block east, in a zig-zag pattern. Any sequence of moves to the north and moves to the east, as long as there are 16 of each move, would get them to the destination. Of course we only ever move to the east or to the north, as anything else would be inefficient and take longer than 32 total moves to reach the destination. It turns out, there are 601,080,390 unique ways to reach the destination in this manner.

Suppose you know that certain intersections are undergoing construction, and are thus not suitable for travel at all. This reduces the number of possible ways to reach the desired destination. You are given int[] x and int[] y, where each point (x[i], y[i]) is an intersection that is under construction. Assuming all movements are a single block to the north or east, return the number of ways to reach the destination without passing any construction points.

Definition

Class:: ManhattanConstruction
Method:: pathCount
Parameters:: int[], int[], int, int
Returns:: int
Method signature:: int pathCount(int[] x, int[] y, int endX, int endY)
(be sure your method is public)

Constraints

x and y will contain between 0 and 50 elements, inclusive, and will have the same number of elements.
endX and endY will be between 0 and 16, inclusive.
Each element of x will be between 0 and endX, inclusive.
Each element of y will be between 0 and endY, inclusive.
Each point (x[i], y[i]) will be unique.

Examples

```
{}
```
```
{}
```
```
1
```
```
1
```
```
Returns: 2
```
You can go North then East, or East then North.
```
{1}
```
```
{1}
```
```
2
```
```
2
```
```
Returns: 2
```
We can do NNEE or EENN, but any other path would go through the the intersection that is under construction.
```
{}
```
```
{}
```
```
16
```
```
16
```
```
Returns: 601080390
```
The example mentioned in the problem statement.
```
{3}
```
```
{3}
```
```
3
```
```
3
```
```
Returns: 0
```
You can't step onto the destination, sadly.
```
{0}
```
```
{0}
```
```
3
```
```
3
```
```
Returns: 0
```
Can't even leave the starting point.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.