Bubble breaker is a popular game on mobile phone.
It is simple but interesting. The gameboard consists of a
screen of differently-colored bubbles arranged in a matrix.
There are five different colors: red, blue, green, yellow and
purple. The player then clicks on any two or more
connecting same-colored bubbles to eliminate them from
the matrix, earning an appropriate amount of points in the
process. The more bubbles eliminated one time, the higher
the points added to the player's score. More specifically,
the rules of the game are as follows:
1). Bubbles are 4-connected to their horizontal and
vertical neighbors. Two or more connecting bubbles with
the same color can be broken at once;
2). Once some bubbles are broken, other bubbles on
top of them fall downwards. Whenever the player clears an
entire bubble column, the columns on its left slide right and
fill the gap.
3). The scoring of each bubble-breaking operation can be expressed in the
formula "Y=X(X-1)". X represents the amount of bubbles broken together, Y is the
resulting score. For example an elimination of 16 bubbles will result in 240 points
(240=16(16-1)).
John likes the game very much. And he has worked out a simple strategy to win
high scores for most cases. In his strategy, John assigns different priorities to bubbles
with different colors. If there are more than one set of connected bubbles with
different colors that can be broken in the gameboard, John always breaks red bubbles
at first, and then green bubbles, then blue bubbles, then yellow bubbles, and finally
purple bubbles. If there are multiple choices with the same color, John can always
break the proper bubbles and achieve a final score as high as possible. Now the
problem is, given a new bubble breaker game, what final score can John win using his
strategy?
The input consists of multiple test cases.
Each test case starts with a line containing two integers N and M (1<=N<=16,
1<=M<=11), which are the number of rows and columns of the gameboard. Each of
the following N lines contains M integers, ranging from 0 to 4, representing the
bubbles in the gameboard with different colors (0 = red, 1 = green, 2 = blue, 3 =
yellow, 4 = purple).
The last test case is followed by a line containing two zeros.
For each test case, print a line containing the test case number (beginning from 1)
followed by an integer which is the final score that John will get.
4 3 0 1 2 1 2 3 3 4 0 1 0 0 4 4 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 0 0
Case 1: 10 Case 2: 0
Migrated from old NTUJ.
2009Hefei
| No. | Testdata Range | Score |
|---|