MovingByPoints | Topcoder Archive

Problem Statement

You are given N points. The points are numbered from 0 to N-1. Point i has coordinates (X[i], Y[i]). Note that the given points are not necessarily distinct.

You have to move from point 0 to point N-1. You have to move in steps. In each step you can move by 1 unit of distance in one of the four cardinal directions. That is, if you are at coordinates (x,y), you can move to (x-1,y), (x+1,y), (x,y+1), or (x,y-1). Additionally, you can only step on points, you cannot enter coordinates that don't contain a point.

For the given N points it may be impossible to get from point 0 to point N-1 according to the above rules. Compute and return the smallest number of additional points that have to be added to the collection in order to be able to do that.

Definition

Class:: MovingByPoints
Method:: countMinimumPoints
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int countMinimumPoints(int N, int[] X, int[] Y)
(be sure your method is public)

Constraints

N will be between 1 and 500, inclusive.
X and Y will each have exactly N elements.
Each element of X and Y will be between 1 and 10^6, inclusive.

Examples

```
3
```
```
{1,2,3}
```
```
{1,2,3}
```
```
Returns: 2
```
You want to be able to walk from (1,1) to (3,3). In order to be able to do that, you need to add two more points. One of multiple optimal solutions is to add the points (2,1) and (2,3).
```
4
```
```
{1,1,1,3}
```
```
{1,2,3,3}
```
```
Returns: 1
```

{1,1,1,2,3,3,4,5,5,5}

{1,2,3,3,3,2,2,2,3,4}

Returns: 0

{2,3,4,5,6,6,5}

{2,1,1,1,2,3,4}

Returns: 3

```
2
```
```
{2,2}
```
```
{2,2}
```
```
Returns: 0
```
Here you want to travel from (2,2) to (2,2). That is trivially possible, without having to add more points. Note that the point (2,2) is given twice. This has exactly the same effect as if it were given only once.

{260522,436426,648772,933447,703497,407775,963982,968417,631932,895728,723857,286918,539679,63340,361868,287940,224593,836991,823355,11431}

{914575,979445,690081,190629,47202,894325,804784,302156,735902,78537,330739,329211,238506,686568,660016,296263,601449,890310,177068,8580}

Returns: 1155084

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.