Problem Statement
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
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
689
731
249
97
599
237
Returns: 4
1000
2000
123
456
123
456
Returns: 0
238
264
23
23
220
29
Returns: 4
436
479
396
118
356
395
Returns: 4
571
626
425
30
25
150
Returns: 4
498
504
140
109
289
40
Returns: 4
697
731
235
658
609
429
Returns: 4
595
619
369
502
585
176
Returns: 4
101
111
21
83
39
3
Returns: 4
210
230
56
7
11
179
Returns: 4
89
91
14
68
36
7
Returns: 4
475
506
362
40
25
124
Returns: 4
714
759
618
604
500
64
Returns: 4
627
652
102
410
261
31
Returns: 4
415
434
295
25
119
86
Returns: 4
676
754
647
114
38
10
Returns: 4
590
624
386
509
514
112
Returns: 4
469
497
373
98
90
111
Returns: 4
964
1020
475
64
153
691
Returns: 4
524
580
92
1
453
126
Returns: 4
70
75
3
26
59
15
Returns: 4
451
499
423
388
46
406
Returns: 4
180
173
148
124
48
4
Returns: 3
365
363
66
139
281
290
Returns: 3
152
142
91
125
69
13
Returns: 3
549
558
23
316
539
214
Returns: 3
530
512
226
450
134
57
Returns: 3
526
502
89
336
430
5
Returns: 3
400
361
310
80
198
305
Returns: 3
549
487
179
125
525
242
Returns: 3
768
709
9
453
555
240
Returns: 3
111
83
83
45
47
68
Returns: 3
133
128
100
98
39
25
Returns: 3
179
190
7
72
172
8
Returns: 3
987
880
219
531
721
693
Returns: 3
964
1199
18
143
963
856
Returns: 3
417
346
340
326
62
184
Returns: 3
920
739
600
625
439
335
Returns: 3
386
379
310
148
215
377
Returns: 3
38
40
1
11
37
22
Returns: 3
525
414
380
127
137
413
Returns: 3
114
102
95
81
76
30
Returns: 3
569
305
244
143
132
118
Returns: 2
559
375
397
48
245
47
Returns: 2
779
759
410
674
374
678
Returns: 2
545
502
195
504
512
253
Returns: 2
151
125
116
123
40
135
Returns: 2
899
415
537
112
294
128
Returns: 2
439
324
259
282
118
304
Returns: 2
358
203
234
33
68
114
Returns: 2
718
359
412
471
335
635
Returns: 2
448
121
48
176
11
270
Returns: 2
880
150
436
858
457
781
Returns: 2
423
302
84
234
143
73
Returns: 2
161
78
100
94
73
70
Returns: 2
75
22
36
33
26
36
Returns: 2
461
169
362
409
270
290
Returns: 2
935
776
728
686
799
420
Returns: 2
253
142
158
15
132
11
Returns: 2
773
648
719
226
303
714
Returns: 2
154
121
103
125
66
97
Returns: 2
523
287
373
379
270
420
Returns: 2
729
173
334
156
45
364
Returns: 1
77
59
4
75
73
56
Returns: 1
811
45
467
310
634
272
Returns: 1
889
437
815
147
506
650
Returns: 1
308
196
24
287
25
18
Returns: 1
547
290
140
139
98
523
Returns: 1
384
43
96
324
228
117
Returns: 1
301
246
296
179
26
128
Returns: 1
719
171
443
692
112
59
Returns: 1
285
130
248
197
91
121
Returns: 1
438
400
409
225
20
63
Returns: 1
280
104
73
277
223
52
Returns: 1
518
118
158
113
474
221
Returns: 1
216
61
45
17
182
0
Returns: 1
224
72
217
217
80
220
Returns: 1
958
208
437
592
795
78
Returns: 1
422
112
88
400
75
151
Returns: 1
347
49
256
285
60
101
Returns: 1
969
506
794
774
131
356
Returns: 1
367
182
138
8
319
248
Returns: 1
502
36
390
178
395
267
Returns: 1
961
1348
19
895
418
572
Returns: -1
655
441
456
80
429
373
Returns: 2
287
84
96
68
201
164
Returns: 1
554
191
139
65
339
209
Returns: 1
15
17
1
14
14
6
Returns: -1
332
357
192
306
256
262
Returns: 2
769
571
312
144
453
504
Returns: 3
184
94
144
48
87
84
Returns: 2
466
330
168
10
46
429
Returns: 1
54
59
3
41
13
33
Returns: -1
77
103
24
27
34
57
Returns: -1
97
143
56
94
15
68
Returns: -1
84
73
80
48
46
27
Returns: -1
64
51
48
54
35
38
Returns: 2
66
15
34
11
6
27
Returns: 1
43
28
35
12
9
2
Returns: 2
55
44
10
9
12
42
Returns: 2
77
99
49
32
55
8
Returns: -1
90
19
43
75
61
60
Returns: 1
4
5
2
1
3
2
Returns: -1
4
1
0
0
1
3
Returns: 1
4
3
1
2
1
2
Returns: 0
1
1
0
0
0
0
Returns: 0
6
12
5
4
1
4
Returns: -1
6
1
1
5
2
4
Returns: 1
2
4
0
1
0
1
Returns: 0
5
1
1
2
4
0
Returns: 1
5
3
0
1
4
2
Returns: 1
2
4
1
0
1
1
Returns: -1
100
101
0
0
0
99
Returns: 2
20
12
4
8
15
8
Returns: 2
98
108
26
10
5
97
Returns: 4
100
111
10
10
90
10
Returns: -1
11
11
0
1
0
6
Returns: 4
1000
1100
100
100
100
900
Returns: 4
999
1115
0
0
998
0
Returns: 2
61
67
31
60
32
1
Returns: 4
101
110
1
1
1
100
Returns: 2
11
11
0
4
0
6
Returns: 4
90
90
0
0
89
0
Returns: 2
1000
1053
700
999
300
999
Returns: 4
1000
1116
789
790
789
209
Returns: 4
26
26
19
21
6
23
Returns: 4
999
1115
498
1
500
1
Returns: 4
11
11
7
9
9
3
Returns: 4
14
14
9
0
0
2
Returns: 4
100
140
0
0
0
99
Returns: -1
1000
1000
0
0
999
0
Returns: 2
100
100
75
24
75
75
Returns: 4
101
101
1
1
99
1
Returns: 2
997
1113
1
1
995
1
Returns: 4
995
1111
0
496
0
498
Returns: 4
1000
1
500
500
501
501
Returns: 1
11
11
0
1
0
10
Returns: 3
1000
1100
0
0
0
999
Returns: 2
13
13
0
8
11
12
Returns: 3
1000
1200
0
0
700
700
Returns: -1
13
13
12
9
12
1
Returns: 3
11
11
0
10
10
10
Returns: 2
1000
1150
0
0
0
999
Returns: -1
1000
1115
200
200
800
200
Returns: 4
100
1
0
0
0
0
Returns: 0
4
4
3
0
3
3
Returns: -1
1000
560
230
500
770
500
Returns: 2