Description
Flip game 3D is played on a cube H x N x M with two-sided pieces placed on each of its H x N x M slots. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip some pieces, thus changing the colors of their upper sides from black to white and vice versa. The pieces to be flipped on the H x N x M field are chosen every round according to the following rules:
- Choose any one of the H x N x M pieces.
- Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, to the bottom, to the front, and to the back of the chosen piece (if there are any). That is, depending on the position of the chosen piece, there can be totally 4 to 7 pieces flipped.
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
If it's impossible, print "oops".
Useful Info.
-
3D Cubic Structure char s[H+2][N+2][M+2];
-
Sequential Piece Numbering
-
Sequential Piece Numbering: Generalized
Input
The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.
For each test case:
- The first line gives three integers H, N and M (1 ≤ max(H,N,M) ≤ 20).
- The remainder gives H rectangles, each of which is represented by N lines, where each line consists of M ‘w’ or ‘b’ characters separated by spaces.
Limit:
+(1D)Testcase 1: H = 1, N = 1, M ≤ 4
+(1D)Testcase 2: H = 1, N = 1, M ≤ 16
*(1D)Testcase 3: H = 1, N = 1, M ≤ 20
+(2D)Testcase 4: H = 1, N ≤ 2, M ≤ 2
+(2D)Testcase 5: H = 1, N ≤ 4, M ≤ 4
*(2D)Testcase 6: H = 1, N ≤ 8, M ≤ 8
*(2D)Testcase 7: H = 1, N ≤ 15, M ≤ 15
+(3D)Testcase 8: H ≤ 2, N ≤ 2, M ≤ 2
+(3D)Testcase 9: H ≤ 2, N ≤ 3, M ≤ 3
*(3D)Testcase 10: H ≤ 2, N ≤ 4, M ≤ 4
*(3D)Testcase 11: H ≤ 3, N ≤ 4, M ≤ 4
*(3D)Testcase 12: H ≤ 4, N ≤ 4, M ≤ 4
Note:
The testcases marked "+" can be solved following the brute-force enumeration method used in the practice problem "13402 - Flip Game", while those marked "*" need a more efficient method!
Output
For each test, output the minimum number of rounds to reach a winning configuration, in case such a configuration exists, or the word "oops".