FrogSquare
SRM 729 · 2018-02-08 · by cgy4ever
SRM 729 · 2018-02-08 · by cgy4ever · Brute Force
Problem Statement
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 theint s 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.
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
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
0)
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).
1)
100 5 0 0 3 4 Returns: 1
This time we can jump to (3, 4) directly.
2)
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).
3)
10 7 4 4 5 5 Returns: 3
4)
1 1 0 0 0 0 Returns: 0
Submissions are judged against all 152 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FrogSquare with a public method int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) · 152 test cases · 2 s / 256 MB per case