Problem Statement
You are standing on the cell (0, 0) of an infinite square grid.
Elsewhere in the grid is a rectangular obstacle. The obstacle covers all cells (x, y) such that x1 <= x <= x2 and y1 <= y <= y2.
The value y1 is positive, the value x1 is non-positive, and the value x2 is non-negative. This means that if you went in the positive y direction, you would eventually hit the obstacle.
From your starting cell (0, 0) you are allowed to take between 0 and s steps, inclusive. In each step you can move between two cells that share a side. Obviously, you cannot enter cells covered by the obstacle. Return the number of cells you can reach.
Definition
- Class:
- RectangularObstacle
- Method:
- countReachable
- Parameters:
- int, int, int, int, int
- Returns:
- long
- Method signature:
- long countReachable(int x1, int x2, int y1, int y2, int s)
- (be sure your method is public)
Constraints
- The x-coordinates will satisfy -10^6 <= x1 <= 0 <= x2 <= 10^6.
- The y-coordinates will satisfy 1 <= y1 <= y2 <= 10^6.
- s will be between 0 and 10^9, inclusive.
Examples
-5
5
3
3
2
Returns: 13
The situation is shown below: X denotes the obstacle, S your starting position, * other cells you can visit, and . cells you cannot visit because they are too far. XXXXXXXXXXX .....*..... ....***.... ...**S**... ....***.... .....*..... ...........
-5
5
3
3
3
Returns: 24
The same situation as in Example 0 but we can do one more step. Note that walking into the obstacle is forbidden. XXXXXXXXXXX ....***.... ...*****... ..***S***.. ...*****... ....***.... .....*..... ...........
-4
1
1
2
6
Returns: 61
........*..... .......***.... ..XXXXXX***... .*XXXXXX****.. ******S******. .***********.. ..*********... ...*******.... ....*****..... .....***...... ......*....... .............. A fairly general case in which we can go partially around the obstacle.
0
0
1
1
4
Returns: 38
........... ....*.*.... ...*****... ..***X***.. .****S****. ..*******.. ...*****... ....***.... .....*..... ........... A nice, vaguely heart-shaped area.
-100
100
42
47
0
Returns: 1
If you cannot move, the only cell you can visit is the starting cell.
-291753
6290
363
1089
26198
Returns: 1073286347
-35
104
6552
6855
747
Returns: 1117513
-1
1
2
3
14
Returns: 407
-1
1
2
3
5
Returns: 51
-21
36
5
6954
14
Returns: 321
-736
2417
1232
1234
166585
Returns: 55497884027
-1
4
2
3
6
Returns: 66
-400000
100000
200000
300000
1200000
Returns: 2750000799998
-1
4
2
3
8
Returns: 117
-1
715
1713
90031
13887847
Returns: 385744553038926
-57
1
7
8
62594
Returns: 7836142511
-369
11
8072
8404
16881
Returns: 569834332
-23326
9
220374
267489
3
Returns: 25
-4
1
2
3
13
Returns: 333
-4
1
2
3
4
Returns: 33
-2304
15624
1551
117753
4431
Returns: 31142400
-37
6
127993
142174
3
Returns: 25
-15
225958
933
1008
12
Returns: 313
-46
763
27555
27582
10
Returns: 221
-1
1
2
3
13
Returns: 351
-1
1
2
3
4
Returns: 34
-900
286
6
23607
129150
Returns: 33331170553
-400000
100000
200000
300000
1000000
Returns: 1870000399998
-8
3441
16
451
34
Returns: 2075
-1
4
2
3
7
Returns: 89
-1
4
2
3
9
Returns: 150
-6746
25950
47
102
207
Returns: 60192
-1
137726
1836
212305
5855376
Returns: 68541879750437
-158
25
64884
91400
15560
Returns: 484258321
-98675
11
1471
41457
13976
Returns: 312341334
-32
16176
59509
61300
210210
Returns: 88346794411
-2169
4762
181
99491
628
Returns: 589321
-400000
100000
200000
300000
500000
Returns: 435000350001
-60686
195
1071
8950
712507
Returns: 1014830335649
-4
1
2
3
12
Returns: 281
-4
1
2
3
7
Returns: 89
-188
112601
24315
24318
3448
Returns: 23784305
-127377
1069
182
3997
43
Returns: 3785
-45134
16805
3061
8623
45390786
Returns: 4120645136527325
-968
1257
21
452
304
Returns: 104785
-18604
7
288
333
236
Returns: 111865
-1
1
2
3
12
Returns: 299
-1
1
2
3
3
Returns: 21
-14
13987
1012
1030
80880
Returns: 13082624883
-1
4
2
3
10
Returns: 189
-331
4
160
164
19
Returns: 761
-400000
100000
200000
300000
300000
Returns: 170000400000
-2
242
6
187717
1216
Returns: 2692456
-4
1
2
3
6
Returns: 66
-45708
518
8
373
228765
Returns: 104602942957
-3
166
202679
202686
1130
Returns: 2556061
-915
4387
100758
100788
4926
Returns: 48540805
-223
13
5
16
37
Returns: 1935
-25859
565
550
557
484959
Returns: 470341948361
-122929
406
12
22
13707
Returns: 364662105
-400000
100000
200000
300000
1400000
Returns: 3790001199998
-4446
43
7
9186
246
Returns: 83231
-1837
5
54595
54607
38843
Returns: 3017634985
-4
15198
15123
15143
7864
Returns: 123700721
-1
1
2
3
11
Returns: 251
-2549
118028
9
14950
158403
Returns: 47779713249
-16398
14
6
7
2
Returns: 13
-2804
63
4
7902
7969649
Returns: 127030603292329
-81201
178
1
1315
50
Returns: 2601
-1
4
2
3
11
Returns: 233
-1710
14
10494
10501
188
Returns: 71065
-400000
100000
200000
300000
900000
Returns: 1490000199998
-4
557
1
2836
187448
Returns: 70272280893
-258340
346684
47
466
127
Returns: 25952
-46
215061
185059
185197
3606
Returns: 26013685
-336
440
21
26
74597463
Returns: 11129563120965769
-147442
693
48582
56561
1
Returns: 5
-4
1
2
3
14
Returns: 389
-4
1
2
3
9
Returns: 150
-139
7800
157211
295228
248604
Returns: 122913160111
-101546
24752
1262
1455
48720637
Returns: 4747395985125025
-75
458
111131
111133
830
Returns: 1379461
-400000
100000
200000
300000
400000
Returns: 285000450000
-7188
50
1
81
189478
Returns: 71802884288
-82219
940
259016
259017
677232
Returns: 917132813753
-775
17245
705
706
49
Returns: 4901
-1
1
2
3
10
Returns: 207
-182447
137
26
39
463249
Returns: 429147286663
-400000
100000
200000
300000
700000
Returns: 860000200001
-1
4
2
3
3
Returns: 21
-1
4
2
3
12
Returns: 281
-219766
2
3
11
6
Returns: 70
-4
1
2
3
8
Returns: 117
-4
1
2
3
3
Returns: 21
-15045
4086
279
48102
463
Returns: 395440
-31253
1
74211
75224
80495
Returns: 12953169548
-30816
1136
31
32
15686
Returns: 457794555
-16230
1
1124
10972
20448
Returns: 699187072
-137306
180692
553
1056
4656
Returns: 26523169
-3
753
979
1022
210439
Returns: 88569526981
-63
61554
7
108455
11413
Returns: 194753812
-1
1
2
3
9
Returns: 167
-400000
100000
200000
300000
1300000
Returns: 3250000999998
-1
1
2
3
7
Returns: 99
-6821
225475
9
14107
3
Returns: 25
-306
712
42204
42227
6211541
Returns: 77166495150207
-3
29712
1208
1679
2450
Returns: 11526793
-8579
8
502
133968
1899
Returns: 6227152
-1
4
2
3
4
Returns: 33
-1
4
2
3
13
Returns: 333
-756
199646
2212
55440
469488
Returns: 429869386420
-304
22
455
467
224841
Returns: 101107381964
-724
3
89
65310
7
Returns: 113
-400000
100000
200000
300000
800000
Returns: 1150000000002
-2
5658
14202
91366
3436
Returns: 23619065
-89070
157987
554
1957
7
Returns: 113
-46809
1844
3
1732
1
Returns: 5
-13
9158
1407
17279
127793
Returns: 32516513677
-4
1
2
3
11
Returns: 233
-1
2
65976
65978
7897
Returns: 124741013
-3566
22
17515
18333
10007
Returns: 200300113
-14
2969
768
1870
23738343
Returns: 1127017900867533
-63
44
4535
58719
150640
Returns: 45379262741
-45788
19
27
116990
12
Returns: 313
-400000
100000
200000
300000
1100000
Returns: 2290000599998
-28
5932
119742
142102
461
Returns: 425965
-1
1
2
3
8
Returns: 131
-16071
1326
387
2248
11
Returns: 265
-1
1
2
3
6
Returns: 72
-1210
1902
111693
233000
30672
Returns: 1881604513
-608
50494
1602
1720
6
Returns: 85
-2
510480
1
2
468
Returns: 435259
-838
12268
1453
1497
138
Returns: 38365
-1
4
2
3
5
Returns: 48
-1
4
2
3
14
Returns: 389
-63
127
124989
124990
41
Returns: 3445
-400000
100000
200000
300000
600000
Returns: 625000250001
-218
1365
17124
17139
25453
Returns: 1295137673
-150
240984
834
3368
6
Returns: 85
-1
14
737
12038
5
Returns: 61
-96477
31268
2
30
22517
Returns: 507105357
-4
1
2
3
10
Returns: 189
-4
1
2
3
5
Returns: 48
-100
100
42
47
1000000000
Returns: 2000000001999978393
-90
150
400
500
10000000
Returns: 200000019948178
-896489
976548
143548
797896
999777888
Returns: 1999108676113668583
-1000000
900000
1000
1000000
1000000000
Returns: 1999996303893300998
-1
111
111
11111
111111111
Returns: 24691358196287304
-999999
999996
2
999997
999999999
Returns: 1999995998017999985
-123456
234567
10
999999
1000000000
Returns: 1999999586061457089
-1
1
1
1
1000000000
Returns: 2000000001999999990
-23
432434
1
999999
999999999
Returns: 1999999565521675579
-31823
23123
33
23912
10000323
Returns: 200010156278593
-250000
249990
250000
750000
2000000
Returns: 7625012000028
-1000000
1000000
1
1000000
1000000000
Returns: 1999996001994999999
-10000
1000000
1111
222222
1000000000
Returns: 1999999758674638887
0
999999
1
1
1000000000
Returns: 2000000001997000001
-1000000
1000000
1
1
1000000000
Returns: 1999998001993999998
-4
10
1
8
1000000000
Returns: 2000000001999999771
-3
0
1
2
3
Returns: 19
-1
1
1
1000000
1000000000
Returns: 2000000001996999993
-5
5
3
3
1000000000
Returns: 2000000001999999918
-10
0
1
1
2
Returns: 10
-3
0
1
4
16
Returns: 521
-1000000
1000000
49
1000000
1000000000
Returns: 1999996002091000047
-1000000
1000000
10000
100000
1000000000
Returns: 1999997821993909998
-3
0
1
1
16
Returns: 533
-100
1000
100
1000
1000000000
Returns: 2000000001998805798
-100
1123
134
24444
1000000000
Returns: 2000000001970016289
0
5
1
1000000
1000000000
Returns: 2000000001993999989
-41
17
35
35
2657356
Returns: 14123087134614
-10000
10000
101010
200000
1000000000
Returns: 1999999999820041008
-10
0
1
4
2
Returns: 10
-1
10
3
3
20
Returns: 785
-1000000
999900
500000
1000000
1000000000
Returns: 1999997002243500298
-123123
234234
345345
456456
1000000000
Returns: 1999999904613337625
-76
4
9
35
56
Returns: 5147
-10
0
1
1
15
Returns: 448
0
2
1
1
10
Returns: 212
-346068
875203
678323
683797
862183215
Returns: 1486719181731428529
-10
10
1
100
100000000
Returns: 20000000199997659
-4
6
7
14
23
Returns: 956
-999888
888999
111222
999777
999777888
Returns: 1999108196481629137
-200
20
50
60
999999999
Returns: 1999999997999989128
-12345
67890
111213
141516
987654321
Returns: 1950922113447414409
-10
10
10
20
35
Returns: 2097
-1
9
10
31
999999987
Returns: 1999999950000000031
-4595
2660
730
4506
17906
Returns: 589419661
-123456
987654
159263
951847
999999999
Returns: 1999998873484241396
-1000
1000
200
20000
99999999
Returns: 19999999758374198
-1
0
1
1
8
Returns: 139
-9079
1857
3795
9077
18078
Returns: 565891683
-1000000
1000000
100
5000
100000000
Returns: 19997990393995098
-50
50
1
2
75
Returns: 6838
-20
0
1
1
1055178
Returns: 2226803333662