FrogSquare | Topcoder Archive

Problem Statement

We have an n by n board. Both rows and columns are numbered 0 through n-1.

There is a frog on the board. Initially, the frog is located in the cell (sx, sy). Its goal is to reach the cell (tx, ty).

The frog can move by making a sequence of zero or more jumps. Each jump must have length at least d. More precisely, the frog can jump from (r1,c1) to (r2,c2) if and only if the Euclidean distance between the centers of those two cells is at least d. Formally, sqrt( (r1-r2)^2 + (c1-c2)^2 ) must be greater than or equal to d.

The frog is not allowed to jump outside the board.

You are given the ints n, d, sx, sy, tx, and ty. Compute and return the minimum number of jumps the frog needs to make to reach its goal. If the goal cannot be reached, return -1 instead.

Definition

Class:: FrogSquare
Method:: minimalJumps
Parameters:: int, int, int, int, int, int
Returns:: int
Method signature:: int minimalJumps(int n, int d, int sx, int sy, int tx, int ty)
(be sure your method is public)

Constraints

n will be between 1 and 1,000, inclusive.
d will be between 1 and 2,000, inclusive.
sx will be between 0 and n-1, inclusive.
sy will be between 0 and n-1, inclusive.
tx will be between 0 and n-1, inclusive.
ty will be between 0 and n-1, inclusive.

Examples

```
100
```
```
10
```
```
0
```
```
0
```
```
3
```
```
4
```
```
Returns: 2
```
The distance between (0, 0) and (3, 4) is 5, which is less than 10, so we can't jump there direcly. However we can get there in 2 jumps, for example: from (0, 0) to (10, 0), then to (3, 4).
```
100
```
```
5
```
```
0
```
```
0
```
```
3
```
```
4
```
```
Returns: 1
```
This time we can jump to (3, 4) directly.
```
100
```
```
200
```
```
0
```
```
0
```
```
3
```
```
4
```
```
Returns: -1
```
You can't jump to anywhere on the board from (0, 0). Thus you can't get to (3, 4).
```
10
```
```
7
```
```
4
```
```
4
```
```
5
```
```
5
```
```
Returns: 3
```
```
1
```
```
1
```
```
0
```
```
0
```
```
0
```
```
0
```
```
Returns: 0
```

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.