Problem Statement
You are given a rectangular board consisting of width times height small squares. Return the number of different ways there are to cut a k-polyomino out of this board, so that the remaining part remains connected.
A k-polyomino is a connected set of k squares. The figure below shows as an example all possible pentominoes (5-polyominoes) ignoring any translations, rotations or reflections.
Connected means side-connected here (both in the polyomino definition and in the requirement for the remaining part of the board) - i.e., you must be able to go from any square to any other by only going through squares and square-sides but not square-corners.
For two ways of cutting a polyomino out of the grid to be different and be counted separately it suffices if at least one grid square is included in the first polyomino but not in the other.
The example below shows some polyomino cuts for k=7. The two on the left (red) are not counted, since they leave the remaining grid disconnected, while the one on the right (green) is counted.
Definition
- Class:
- PolyominoCut
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int k, int width, int height)
- (be sure your method is public)
Constraints
- k will be between 1 and 8, inclusive.
- width and height will be between k+1 and 800, inclusive.
Examples
1
10
20
Returns: 200
There is only one 1-polyomino (called monomino), and this can be cut out anywhere on the grid.
3
10
10
Returns: 480
There are in total 484 ways to cut a triomino (3-polyomino) out of a 10x10 square, but 4 of them leave a square in the corner not connected (see figure below), so only 480 satisfy the problem requirements.
8
800
800
Returns: 1704053350
The worst case fits in an int.
8
780
778
Returns: 1615412228
8
776
16
Returns: 26549726
8
27
780
Returns: 49621537
8
28
13
Returns: 644987
7
792
782
Returns: 464897376
7
766
18
Returns: 8768680
7
14
766
Returns: 6460760
7
17
29
Returns: 279268
6
769
779
Returns: 128600036
6
798
24
Returns: 3715016
6
25
771
Returns: 3754948
6
12
12
Returns: 19460
5
792
767
Returns: 38080134
5
800
27
Returns: 1260006
5
10
779
Returns: 394612
5
18
21
Returns: 19156
4
793
778
Returns: 11678147
4
796
27
Returns: 385313
4
26
791
Returns: 367887
4
27
11
Returns: 4588
3
777
774
Returns: 3599082
3
772
16
Returns: 69384
3
17
800
Returns: 76698
3
20
21
Returns: 2274
2
793
781
Returns: 1237092
2
780
16
Returns: 24164
2
27
780
Returns: 41313
2
25
21
Returns: 1004
1
762
774
Returns: 589788
1
763
18
Returns: 13734
1
11
777
Returns: 8547
1
25
13
Returns: 325
1
184
277
Returns: 50968
8
515
303
Returns: 411826908
8
48
754
Returns: 90278720
3
769
61
Returns: 276474
3
358
519
Returns: 1109550
8
27
51
Returns: 3046456
2
255
795
Returns: 404400
7
480
567
Returns: 203541404
7
417
130
Returns: 39829204
1
353
497
Returns: 175441
3
75
10
Returns: 3990
6
340
237
Returns: 17109394
4
74
506
Returns: 695205
7
741
370
Returns: 204925540
5
46
20
Returns: 50008
7
800
800
Returns: 480458296
6
800
800
Returns: 137418292
5
800
800
Returns: 40124900
4
800
800
Returns: 12115209
3
800
800
Returns: 3830400
2
800
800
Returns: 1278400
1
800
800
Returns: 640000
8
9
9
Returns: 82732
7
8
8
Returns: 18424
6
7
7
Returns: 4080
5
6
6
Returns: 904
4
5
5
Returns: 204
3
4
4
Returns: 48
2
3
3
Returns: 12
1
2
2
Returns: 4