| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1126
Bubble Breaker
Time Limit: 2000ms
Memory Limit: 65536kb Description
 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? Input
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. Output
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.
Sample Input
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 Sample Output
Case 1: 10 Case 2: 0 |