1027 The Same Game

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

さめがめ

問題

「さめがめ」というゲームは、10×15の盤面上で遊ぶ1人用ゲームである。各マスにはそれぞれ、赤(R)、緑(G)、青(B)のどれかの色をもつボールが入っている。ある2つの同じ色のボールについて、同じ色のボールをつたって上下左右にたどることで互いに辿りつくことができるとき、2つのボールは同じクラスターに所属すると言う。ゲームの各ステップにおいて、プレイヤーは2つ以上のボールを持つクラスターを選び、そのクラスターに所属するボールを全て除去する。その後、次の2つのステップによって盤面を「圧縮」する:
1. 各列の残ったボールを、空スペースを無くすように下に詰める。列内のボールの順序は維持される。
2. 列が空になったら、その右側の列を左側に可能なだけ詰める。列の順序は維持される。
例えば、以下の小さな盤面において、左下隅のボールを選ぶと次のようになる:

このゲームの目的は盤面から全てのボールを取り除くことであり、全てのボールが除去されるか、または全てのクラスターが1つのボールしか持たなくなったときにゲームは終了する。各ゲームにおけるスコアの計算は以下のように行う。初期スコアは0である。m個のボールで構成されるクラスタが除去されると、スコアは(m-2)^2増加する。ゲームの終了時に全てのボールが除去されていれば、ボーナスとして1000点が加算される。
あなたは、各ステップについて、可能な最大のクラスターを除去するのが良い戦略であると考え、その戦略を用いた場合のゲームの進行シミュレートするプログラムを書くことでこの戦略をテストしてみたいと思った。もし選べるボールが複数個ある場合は、最大クラスターを与える最も左側のボールを選ぶ。そのようなボールが複数ある場合は、その中で最も下にあるものを選ぶ。

入力

あなたは入力にいくつかのゲームを与えられる。入力の最初の行は与えられるゲームの数をあらわす整数が書かれている。各ゲームの初期状態は上の行から順番に1行ずつ与えられる。各行は「R」「G」「B」の文字によって構成される15文字の文字列を含み、行の左端から順番にそのマスに入っているボールの色を記述している。各ゲームの後には空行が含まれる。

出力

各ゲームについて、ゲーム番号を出力し、空行を出力し、各動きについての情報を出力し、最終スコアについて出力せよ。各動作は次のフォーマットによって出力せよ:

Move x at (r,c): removed b balls of color C, got s points.

ここで、xは動作番号、rとcはそれぞれ選んだボールの位置をあらわす行番号と列番号である。行は下から順番に1から10で番号づけされ、列は左から順番に1から15で番号づけされている。bは除去されたクラスタが持っていたボールの数である。Cは除去されたボールの色をあらわす「R」「G」「B」のうちのどれかである。sはその動作におけるスコアである。その動作の後に1000点ボーナスを獲得したとしてもそれは含まない。
最終スコアは以下のように表示せよ:

Final score: s, with b balls remaining.

各ゲームの出力の間には空行を挿入すること。「balls」および「points」については、それらの指す値が1であっても複数形のまま出力すること。

入力例

3
RGGBBGGRBRRGGBG
RBGRBGRBGRBGRBG
RRRRGBBBRGGRBBB
GGRGBGGBRRGGGBG
GBGGRRRRRBGGRRR
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRGGGGRRRRR
GGGGGGGGGGGGGGG

RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG

RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG

出力例

Game 1:

Move 1 at (4,1): removed 32 balls of color B, got 900 points.
Move 2 at (2,1): removed 39 balls of color R, got 1369 points.
Move 3 at (1,1): removed 37 balls of color G, got 1225 points.
Move 4 at (3,4): removed 11 balls of color B, got 81 points.
Move 5 at (1,1): removed 8 balls of color R, got 36 points.
Move 6 at (2,1): removed 6 balls of color G, got 16 points.
Move 7 at (1,6): removed 6 balls of color B, got 16 points.
Move 8 at (1,2): removed 5 balls of color R, got 9 points.
Move 9 at (1,2): removed 5 balls of color G, got 9 points.
Final score: 3661, with 1 balls remaining.

Game 2:

Move 1 at (1,1): removed 30 balls of color G, got 784 points.
Move 2 at (1,1): removed 30 balls of color R, got 784 points.
Move 3 at (1,1): removed 30 balls of color B, got 784 points.
Move 4 at (1,1): removed 30 balls of color G, got 784 points.
Move 5 at (1,1): removed 30 balls of color R, got 784 points.
Final score: 4920, with 0 balls remaining.

Game 3:

Final score: 0, with 150 balls remaining.

出典

East Central North America 1999