1507 . OmniGravity
Description
In this problem, we will play with four 2 x 2 squared pieces, an 8 x 8 board, few obstacles and gravity(!!!).
Initially the board contains few obstacles and the 4 colored pieces randomly placed. An example of an initial configuration is shown in the above diagram. The black squares represent the obstacles and the 4 colored pieces are shown with labels A, B, C and D - (in order to help the colorblind people). Initially there is no gravity and thus the pieces remain at a steady position. We can enable gravity' in any of the four directions to move the pieces. The pieces move in the direction of gravity. A piece continues to move until it hits an edge of the board, an obstacle or any other piece. The obstacles aren't affected by gravity and so remains in their initial position at all times. We can enable at most onegravity' at a time. The gravitational direction can only be changed when all the pieces are static.
The diagram above shows the positions of the pieces after the `gravity' from the right is enabled.
How many different static states can be reached by enabling at least one `gravity'? Two states are different if there is at least once cell that has a different color. A static state is one in which all the pieces are steady!
Input Format
The first line of input is an integer T (T<=100) that indicates the number of test cases. Each case consists of 8 lines with 8 characters in each line. Every character will be from the set {A, B, C, D, ., #}. Dots(.) represent empty spaces, hashes(#) represent obstacles and the alphabets represents the pieces. The frequencies of each letter (A,B,C,D) will be exactly 4 and each letter will occupy positions so that they form squares of size 2 x 2. There is a blank line before every case.
Output Format
For each case, output the case number followed by the number of different static states that can be reached from the original position by enabling at least one ``gravity".
Sample Input 1
2 ....AA.. ....AA#. ...#.... .CCBB... .CCBB#.. #...##.. .#DD#... ..DD.##. AABBCCDD AABBCCDD ........ ........ ........ ........ ........ ........
Sample Output 1
Case 1: 110 Case 2: 2
Hints
Problem Source
Migrated from old NTUJ.
Regional Dhaka 2010
Subtasks
| No. | Testdata Range | Score |
|---|