Problem Statement
A checkerboard is a rectangular board divided into R times C unit square cells. The cells are colored alternately black and white. The cell in the top left corner is black.
Black cells of a checkerboard are used to play checkers (also called draughts) and various other similar games. An action shared by many such games is that the pieces can jump each other: whenever a diagonal of the board contains three consecutive cells with the pattern [piece #1], [piece #2], [an empty cell], piece #1 can jump over piece #2 and land on the empty cell. (After such an action piece #2 is sometimes removed from the board, but this will not matter in our problem.)
A configuration is a set of identical pieces, each on a different black square of the checkerboard.
A configuration is jumpy if there is at least one way to make a jump, as described above.
Count all jumpy configurations and return their count modulo 10^9 + 7.
Definition
- Class:
- JumpyCheckers
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int R, int C)
- (be sure your method is public)
Constraints
- R will be between 1 and 20, inclusive.
- C will be between 1 and 20, inclusive.
Examples
3
3
Returns: 12
The jumpy configurations look as follows (each in four possible rotations around the center): O.* O.* O.* .O. .O. .O. *.* O.* O.O (Above, 'O' denotes a piece, '*' an empty black cell, and '.' a white cell. The white cells are completely unused)
2
13
Returns: 0
There is no three-cell diagonal on this board, so no configuration can be jumpy.
4
5
Returns: 774
1
1
Returns: 0
1
17
Returns: 0
17
1
Returns: 0
17
2
Returns: 0
20
20
Returns: 421573493
19
20
Returns: 562079871
20
18
Returns: 451922307
17
20
Returns: 525314478
20
16
Returns: 971788059
15
20
Returns: 283909430
20
12
Returns: 869117720
9
20
Returns: 785358769
20
3
Returns: 58116817
19
19
Returns: 278529275
19
18
Returns: 285898773
17
19
Returns: 629166238
15
19
Returns: 410567307
18
18
Returns: 692435197
18
17
Returns: 894349043
18
11
Returns: 775546188
17
17
Returns: 559408666
17
12
Returns: 611759902
8
17
Returns: 915174719
16
16
Returns: 22513555
15
16
Returns: 337953230
14
16
Returns: 714773661
13
16
Returns: 367822428
9
7
Returns: 291223721
4
17
Returns: 162123272
3
14
Returns: 1972152
13
3
Returns: 986076