Problem Statement
Time limit: 3 seconds.
Your company produces a sliding puzzle. The frame of the puzzle is a solid boundary of a R times C rectangle. Inside the rectangle is a grid of unit square cells. Some cells are blocked, others contain movable tiles, the rest is empty.
There are exactly N movable tiles, and they are labeled using the first N digits, starting from 0.
The initial state of the puzzle is given in the
An example initial state of a puzzle with R=2 rows and C=3 columns is shown below. Blocked cells are denoted 'X', tiles have numbers, empty cells are periods ('.').
+---+---+---+ | 1 | 2 | 3 | +---+---+---+ | X | . | 0 | +---+---+---+
The puzzle is played by sliding the movable tiles. In each move you can choose any tile that shares a side with an empty cell and slide that tile into that empty cell. E.g., in the situation shown above there are exactly two possible moves: either you slide the 2 tile down or the 0 tile left. If you slide the 2 tile down, you will get a new configuration in which there are three possible moves: slide 1 right, or 3 left, or 2 back up.
Due to the manufacturing process all pieces may have imperfections which may cause the puzzle to get stuck. You now want to introduce a very thorough process of automated testing that will allow you to detect and discard all defective products.
The testing process must create each reachable configuration of tiles at least once and from each of them it must try each possible move at least once. Only after all of this was tested and the puzzle pieces never got stuck can you be sure that this particular product isn't defective.
A sequence of moves is called a valid test if it satisfies the above requirements. A valid test is optimal if it's the shortest among all possible valid tests.
Count all optimal valid tests. Return their count modulo 10^9 + 7.
Definition
- Class:
- ThoroughTesting
- Method:
- count
- Parameters:
- int, int, int, String[]
- Returns:
- int
- Method signature:
- int count(int R, int C, int N, String[] board)
- (be sure your method is public)
Notes
- Formally, a sequence of moves is a sequence of pairs (number of the tile we move, cardinal direction in which we move it). Two sequences of moves differ if and only if these sequences differ.
- An equivalent way of stating the last constraint ("All non-'X' cells on the board will form one 4-connected component.") is that if we changed any N-1 of the N tiles into empty cells, the remaining tile would be able to reach all the empty cells.
Constraints
- R will be between 1 and 8, inclusive.
- C will be between 1 and 8, inclusive.
- N will be between 1 and 8, inclusive.
- N will be less than R*C.
- (R*C)N will not exceed 1300.
- board will have R elements.
- Each element of board will have C characters.
- Each of the first N digits ('0', '1', ...) will appear exactly once in board.
- Each other character in board will be 'X' or '.'.
- board will contain at least one '.'.
- All non-'X' cells on the board will form one 4-connected component.
Examples
1
4
1
{"0..."}
Returns: 1
In the unique optimal test we slide the 0 tile three times to the right and then three times to the left.
1
4
1
{".0XX"}
Returns: 1
Here the board contains some blocked cells so the unique optimal test is even shorter: one move left, one move right.
2
2
3
{"01", "2."}
Returns: 24
Note that not all 4! configurations of these three tiles are actually reachable by sliding them. (As we go around the square, the three tiles always remain in the same cyclic order.)
2
3
3
{"0.2", "X1X"}
Returns: 6
Not much swapping possible in this puzzle. When doing an optimal test we must shift each tile into the center and back out. We get to choose in which order we want to do that, so that's 3! = 6 possibilities.
2
3
1
{"0..", "X.X"}
Returns: 2
Two options: either we visit the bottom row before the top right corner or vice versa.
4
4
1
{"....", ".XX.", ".XX0", "...."}
Returns: 24
One of the solutions is a full "circle" clockwise and then the same counter-clockwise. Eleven other solutions have the form that we pick an empty cell, go there clockwise, go a full circle counter-clockwise, and then return clockwise to where we started. The other twelve solutions are the previous twelve done in the opposite direction.
4
4
2
{"0...", "..1.", "....", "...."}
Returns: 219051936
4
4
2
{"0...", "..1.", ".X..", "...."}
Returns: 498921911
4
4
2
{"0...", "..1.", "....", ".X.."}
Returns: 811541830
3
4
2
{"....", "..1.", "...0"}
Returns: 918354932
3
3
3
{"021", "...", "..."}
Returns: 216749343
3
3
3
{"021", ".X.", "..."}
Returns: 907674178
3
3
3
{"021", "X..", "..."}
Returns: 38576254
3
3
3
{"0.1", "...", "X2."}
Returns: 633900938
2
3
4
{"031", "2.."}
Returns: 50896868
6
1
4
{"0", ".", "3", "1", "2", "."}
Returns: 109486080
1
6
4
{"0.312."}
Returns: 109486080
8
8
1
{"........", "........", "........", ".....0..", "........", "........", "........", "........"}
Returns: 721095917
8
8
1
{"........", ".XXX....", "........", "..X..0..", "..X.....", "........", "........", ".......X"}
Returns: 575164117
6
6
2
{"......", "..0X1.", "......", "..X...", "...X..", ".X...."}
Returns: 489298440
6
6
2
{"......", "..0.1.", "......", "......", "......", "......"}
Returns: 948740655
2
5
3
{"0.1.2", "....."}
Returns: 678302333
2
5
3
{"0.1.2", ".X.X."}
Returns: 591815779
7
5
2
{".....", ".....", "..1..", ".....", ".....", ".....", "...0."}
Returns: 598584372