Problem Statement
"Knights Out" is a one-player game played on a NxM rectangular board divided into 1x1 squares. Each square on the board can be white or black. Initially all the squares are white.
A knight is a chess piece that moves by simultaneously shifting one square horizontally and two squares vertically, or one square vertically and two squares horizontally. Two squares A and B on the board are called neighboring if it's possible to make a single knight's move to reach B from A.
In one move the player can choose a square on the board and simultaneously change colors of the chosen square and all its neighboring squares (white becomes black and vice versa). The game is finished when all the squares are colored black.
A sequence of moves is called a solution if it transforms the white board into a black one, and there's no cell which is chosen in more than one move. Note that when a cell is chosen, its neighbors which get changed do not also count as being "chosen" in that step. It's not hard to see that the order of moves doesn't matter, so any solution can be viewed as a set of moves. Two solutions are considered distinct if the corresponding sets are distinct. Return the number of distinct solutions modulo 123,456,789.
Definition
- Class:
- KnightsOut
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int M)
- (be sure your method is public)
Constraints
- N and M will each be between 1 and 150, inclusive.
Examples
2
3
Returns: 4
4 possible solutions are listed below ('X' means a square should be chosen and '.' means it shouldn't): XX. .X. XXX .XX XX. XXX .X. .XX
3
3
Returns: 1
The only solution is to choose each square on the board.
7
5
Returns: 16
1
1
Returns: 1
150
150
Returns: 16
6
6
Returns: 16
8
8
Returns: 256
16
16
Returns: 4096
33
33
Returns: 16384
34
34
Returns: 21521878
69
69
Returns: 86087512
70
70
Returns: 41000473
118
118
Returns: 38723623
141
141
Returns: 23360683
142
142
Returns: 103002862
4
2
Returns: 16
4
22
Returns: 256
16
6
Returns: 4096
8
34
Returns: 65536
20
10
Returns: 1048576
12
118
Returns: 16777216
1
2
Returns: 1
3
1
Returns: 1
1
150
Returns: 1
149
1
Returns: 1
1
134
Returns: 1
123
1
Returns: 1
2
2
Returns: 1
5
2
Returns: 4
2
6
Returns: 1
7
2
Returns: 1
2
8
Returns: 1
150
2
Returns: 1
2
149
Returns: 4
148
2
Returns: 16
2
147
Returns: 4
146
2
Returns: 1
2
145
Returns: 1
123
2
Returns: 4
2
134
Returns: 1
3
4
Returns: 1
5
3
Returns: 4
6
3
Returns: 1
4
4
Returns: 1
4
5
Returns: 1
4
6
Returns: 16
6
5
Returns: 4
3
150
Returns: 1
150
4
Returns: 16
149
5
Returns: 1
6
150
Returns: 16
135
136
Returns: 4
136
137
Returns: 4
149
149
Returns: 256
148
148
Returns: 4096
149
148
Returns: 256
149
150
Returns: 1
148
150
Returns: 1
147
148
Returns: 256
147
147
Returns: 64
149
147
Returns: 64
150
147
Returns: 1
99
107
Returns: 1
142
139
Returns: 4
131
105
Returns: 4
141
83
Returns: 1
105
149
Returns: 1
108
141
Returns: 1
55
83
Returns: 16
108
143
Returns: 16
133
10
Returns: 1
121
144
Returns: 1
139
141
Returns: 4
145
108
Returns: 4
105
99
Returns: 1
147
146
Returns: 1
144
143
Returns: 1
139
147
Returns: 1
146
25
Returns: 1
52
133
Returns: 256
134
61
Returns: 4
138
123
Returns: 4
129
87
Returns: 1
73
29
Returns: 4
70
129
Returns: 16
97
61
Returns: 16
142
115
Returns: 64
69
142
Returns: 77502052