|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||1||0||0||0.000%|
John has been playing a lot Bejeweled lately, but he's becoming frustrated at his inability to get high scores. He would like a program to help him play, and you can help!
In Bejeweled, you have a grid of gems of various colors, such as the one below:
BGR GRR BGY
You make a move by switching two gems that are horizontally or vertically connected to each other. So, for example, you could switch the first two gems in the second row, changing the board to this:
BGR RGR BGY
If when you do this, any three gems in a row are the same color, they all disappear at once. So in this example, the three green gems would disappear.
B.R R.R B.Y
It can get a little more complex, though. Additionally, multiple sets of three (or more) can be formed at once. For example:
RGOY RGOG OOYO RGOG YBOB
In this case, swapping the right-most orange in the middle row with the yellow next to it...
RGOY RGOG OOOY RGOG YBOB
... makes a row of 3 and a column of 5, which all disappear...
RG.Y RG.G ...Y RG.G YB.B
... and then, any gems that are above an open space fall down to fill the empty spaces...
...Y RG.G RG.Y RG.G YB.B
... and then any newly formed rows of three or more will also disappear:
...Y ...G ...Y ...G YB.B
This continues until there are no more rows or columns of three or more similar colored gems formed. So, more generally, the process is as follows:
Note: In the actual game, gems fall in from the top to replace removed gems. You do not need to take this into account.
The first line of input will contain the number of test cases, T. Each test case will start with a line containing two integers, N and M, separated by a space. The next N lines will each contain exactly M uppercase letters, each representing one gem. Gems of the same letter are considered to be of the same color.
For each test case, output a line of the form "Case #C: D", where C is the number of the test case, starting from 1, and D is the maximum number of gems that can be removed as a result of a single swap.
3 3 3 BGR GRR BGY 5 4 RGOY RGOG OOYO RGOG YBOB 3 3 ABC DEF GHI
Case #1: 3 Case #2: 13 Case #3: 0