Problem Statement
A bishop is a chess piece that can move any number of squares in any diagonal direction (see diagram below).
The chess board has dimensions xSize * ySize, where the top-left corner of the board has coordinates (0, 0), and the bottom-right corner has coordinates (xSize - 1, ySize -1). The bishop is initially at coordinates (x, y). Find the total number of squares reachable by this bishop in k or less moves. Note, that initial square is always counted as reachable.
Definition
- Class:
- BishopOnTheBoard
- Method:
- countReachableCells
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int countReachableCells(int xSize, int ySize, int x, int y, int k)
- (be sure your method is public)
Constraints
- xSize will be between 2 and 50000, inclusive.
- ySize will be between 2 and 50000, inclusive.
- x will be between 0 and xSize - 1, inclusive.
- y will be between 0 and ySize - 1, inclusive.
- k will be between 1 and 50000, inclusive.
Examples
8
8
0
0
2
Returns: 32
Reachable cells are marked by 'X' on the picture:
8
4
0
0
2
Returns: 12
Reachable cells are marked by 'X' on the picture:
2
2
0
0
1
Returns: 2
Reachable cells are marked by 'X' on the picture:
11
5
0
1
2
Returns: 17
Reachable cells are marked by 'X' on the picture:
278
17
37
11
5
Returns: 912
1500
2
1300
0
500
Returns: 700
2
2
0
0
1
Returns: 2
2
2
0
0
50000
Returns: 2
2
2
1
0
50000
Returns: 2
2
50000
1
0
50000
Returns: 50000
2
50000
1
0
49998
Returns: 49999
2
50000
1
0
49997
Returns: 49998
2
50000
0
0
49997
Returns: 49998
3
50000
0
0
24997
Returns: 74992
3
50000
1
0
24998
Returns: 74994
3
50000
1
0
24999
Returns: 74997
25891
16131
22532
12341
11
Returns: 208823860
2714
778
2614
526
9
Returns: 1055746
27132
48794
13419
24259
40
Returns: 661939404
37249
3712
26202
3388
52
Returns: 69134144
44427
40813
32278
14027
24
Returns: 906599575
27318
9466
14771
4111
22
Returns: 129296094
9305
9623
7344
7177
15
Returns: 44771007
28777
17190
1505
15639
51
Returns: 247338315
46064
34859
5296
13418
38
Returns: 802872488
22384
48296
13766
26198
30
Returns: 540528832
44815
21159
43402
9666
68
Returns: 474120293
15629
27375
5394
10671
18
Returns: 213921937
49800
40039
2123
7738
100
Returns: 996971100
41301
28619
31369
17732
23
Returns: 590996659
3774
44661
475
42192
53
Returns: 84275307
16477
23221
14385
17997
91
Returns: 191306209
30209
32186
4203
3345
7
Returns: 486153437
44246
41453
43670
2504
8
Returns: 917064719
4096
31084
2669
901
71
Returns: 63660032
39582
23083
35935
22098
24
Returns: 456835653
12877
4303
10471
3677
2
Returns: 17912152
1895
31534
934
31080
16
Returns: 27798076
4431
17945
1292
14517
1
Returns: 8861
39944
2876
18676
989
10
Returns: 57439472
42141
2422
12886
1314
7
Returns: 33936365
3493
20889
975
19524
3
Returns: 16404753
36291
4889
30580
4235
6
Returns: 78296972
793
37902
715
27229
43
Returns: 15028143
6750
4126
332
532
1
Returns: 4790
19103
2655
9861
846
5
Returns: 25359232
26075
4526
5772
1096
3
Returns: 36786526
1755
35336
1019
20207
20
Returns: 31007340
2192
9019
111
8726
4
Returns: 8610912
38773
4867
33998
1306
3
Returns: 38900027
4318
9643
361
5347
2
Returns: 20400858
4310
21677
2858
6854
1
Returns: 8619
1677
30636
1113
18395
15
Returns: 25688286
2722
43155
751
856
11
Returns: 39311773
1631
13285
261
9551
1
Returns: 3261
4041
44183
420
43639
8
Returns: 61561112
325
43395
320
12521
129
Returns: 7051687
235
24397
150
1408
8
Returns: 365529
219
48253
190
35397
5
Returns: 209738
19368
203
14170
177
56
Returns: 1663352
118
36670
98
28722
282
Returns: 2163530
21776
464
9873
350
21
Returns: 4364970
59
7914
35
1800
54
Returns: 144280
385
46967
92
42579
52
Returns: 4638234
434
1940
341
1324
3
Returns: 352997
6040
91
2283
67
10
Returns: 76355
40494
104
5847
84
366
Returns: 2105688
397
16722
251
8077
10
Returns: 1457516
11922
446
10159
380
9
Returns: 1224408
35140
454
609
421
4
Returns: 491756
259
7809
147
1928
10
Returns: 559116
444
45328
90
4512
60
Returns: 6837699
310
33339
122
17357
21
Returns: 1941191
17551
130
6333
3
79
Returns: 1069776
365
23462
138
19007
20
Returns: 2092920
14299
358
3480
119
30
Returns: 2494166
12
27704
1
5909
1625
Returns: 142675
19244
13
13485
0
60
Returns: 9295
21
11049
19
9538
127
Returns: 42426
26
48110
20
13609
1470
Returns: 625430
34
44825
3
8821
642
Returns: 509819
32881
31
11374
30
450
Returns: 385338
8459
47
2950
17
90
Returns: 165863
12
17785
1
3324
412
Returns: 47107
24807
45
19226
39
511
Returns: 558157
19
34481
13
18495
593
Returns: 202589
30682
3
7212
0
5130
Returns: 26209
7
23167
2
17458
220
Returns: 9218
37197
33
32093
22
887
Returns: 552186
22
49307
21
24231
1329
Returns: 542377
59
41
27
39
1
Returns: 61
46
38716
4
12857
435
Returns: 745371
21
41695
15
26060
691
Returns: 289956
37217
37
30968
30
510
Returns: 454853
33
10215
27
5511
219
Returns: 168548
8706
28
8001
12
92
Returns: 44374
3
31233
1
25064
3452
Returns: 19608
10
5042
7
2366
133
Returns: 11921
33820
7
8118
5
2299
Returns: 76684
38372
9
15270
3
3511
Returns: 172674
5
293
2
226
14
Returns: 271
10
47713
6
14566
4347
Returns: 238565
7
20694
5
17136
2619
Returns: 67441
9
9339
4
7144
32
Returns: 2261
5
19117
2
17021
2876
Returns: 33994
8
8833
3
4300
544
Returns: 30432
18453
6
12374
0
890
Returns: 26691
7
6122
6
3093
832
Returns: 21427
21286
10
11175
9
1605
Returns: 106430
4
15435
1
13435
1626
Returns: 13753
9
37807
0
25473
4102
Returns: 170131
9
12812
0
8493
826
Returns: 49156
5
31182
1
809
4306
Returns: 45080
26941
8
5184
4
1189
Returns: 54014
32152
7
23829
4
4566
Returns: 112532
45680
6
30349
5
1711
Returns: 51321
50000
50000
0
0
1
Returns: 50000
50000
50000
0
0
2
Returns: 1250000000
50000
10000
0
2000
3
Returns: 116996000
50000
50000
0
0
50000
Returns: 1250000000
49999
49999
0
0
50000
Returns: 1249950001
49999
49999
0
1
50000
Returns: 1249950000
49999
19999
49997
19996
50000
Returns: 499965000
49999
49999
49997
49996
49999
Returns: 1249950000
19999
49999
19997
49996
49997
Returns: 499965000
48999
49999
48997
49996
49997
Returns: 1224950500