2281 Link and Pop -- the Block Game

原文

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

問題

Link and Pop -- the Block Game

最近、ロバートはインターネット上で新しいゲーム（"Link and Pop"の最新バージョン）を見つけました。ゲームのルールは非常に簡単です。最初に、大きさn×mのボードは、n×m個のブロックで埋められます。これらのブロックの各々は、その上にシンボルを持っています。あなたがすべきことは、高々3つの水平または垂直にまっすぐな線分で構成される線で接続される、同じシンボルを持つペアのブロックを見つけることです。線分はボード上の他のブロックを越えることはできませんので注意してください。（Fig.1 にいくつかの可能な接続の例が見えます。いくつかのブロックは既にボード上から削除されていることに注意）

もしそのようなブロックのペアが正常に見つかれば、2つのブロックを一緒にポップ（消す）ことができます。この後、いくつかのブロックは後述のルールに従って新しい位置に移動させることができます。その次に、次のペアの発見を開始できます。ゲームはブロックがなくなるか、そのようなペアが発見できなくなるまで続きます。
　
ブロックは以下のルールに従って移動します。最初に、それらのブロックは"up"、"down"、"left"、"right"、"stand still"といった変化しない移動属性を持っています。あるブロックのペアが削除された後、ブロックはその移動属性の方向に移動させられるか確認するために一つずつチェックされます。一番上の行のブロックが最初にチェックされます。同じ行の中では、左側のブロックが最初にチェックされます。もしブロックの移動属性の方向にある隣接位置が占有されていない場合、ブロックは即座にその位置に移動されます。ブロックはゲームボードの境界を越えて移動することはできません。もちろん、属性"stand still"を持つブロックは常に元の位置にとどまります。すべてのブロックがチェックされた後(これはチェッキングのターンと呼ばれる)、もう1つのチェッキングのターンが開始されます。これは、移動ルールに基づいて新しい位置に移動できるブロックがなくなるまで続きます。各チェッキングのターンでは、各ブロックがチェックされ、移動があるならそれは一度限りであることに注意してください。1つのチェッキングのターンで、ブロックがチェックされて新しい位置へ次々と進めていくことはできません。
　
ロバートは、そのゲームが非常に興味深いと感じた。しかし何度かプレイした後、ボードのサイズがかなり大きい場合、ブロックのペアを見つけるのは非常にタフな作業になることに気づいた。さらに、ポップできるブロックがもうないため、彼はしばしば"Game Over"となった。ロバートは、全てのブロックがポップされていないのは自身のせいではないと感じた。それはブロックが最初にランダムに配置されている場合、ゲームが終わらない可能性が多分にあることだ。しかし、何回もゲームをプレイしてこれを証明するには非常に時間がかかってしまう。そこでロバートは、ゲーム内の行動をシミュレートし、ゲームが終了できるかどうかがわかるプログラムを書くことをあなたに求めています。
　
このようなプログラムを可能にするために、ロバートは次のようにブロックのペアを選択するルールをまとめています。まず、1つのまっすぐな線分で接続されたペアは、簡単に見つけられるため、最初に見つけてポップすべきです。次に、そのようなペアが見つからない場合、2つのまっすぐな線分で接続されたペアを見つけてポップすべきです。最後に、その2種類のペア両方が見つからない場合、3つのまっすぐな線分で接続されたペアを見つけてポップすべきです。同じ数のまっすぐな線分で接続されたペアが複数存在する場合、最も上の行（または2つ以上のブロックが同じ行に配置されている場合、最も左）に配置されたブロックが含まれているペアが最初に選択されます。このルールがまだ連結を壊せない場合（複数のペアが最も上、左の位置にある1種類のブロックを共有することがあるため）、これらのペアにある他方のブロックは同じルールに従って比較されます。Fig.2 は上記のルールに従うミニゲーム"Link and Pop"のトレースを示しています。

入力

入力は30以下のテストケースを含みます。各テストケースの最初の行はボードの大きさを表す2つの整数n, m (1 <= n, m <= 30)を含みます。その後にn行が続きます。これら各々の行は空白で区切られたm個の文字列を含みます。これら各々の文字列は1つのブロックの初期状態を表現します。各文字列は常に2つの大文字で構成されます。最初の文字はブロックのシンボルです。2つ目の文字は常に'U'、'D'、'L'、'R'そして'S'の1つです（それはブロックの移動属性：上、下、左、右そして立ったままを各々示しています）。テストケースの間に空行はありません。入力は2つのゼロの行で終わります。

出力

各テストケースについて、最初にテストケースナンバーを出力してください。その後の行で、あなたはn行(各々m文字を含む)からなるボードの最終状態を出力しなければなりません。ある位置にブロックがあれば、ブロックのシンボルを出力してください。ある位置にブロックがなければ、代わりにピリオドを出力してください。テストケースの間に空行を出力しないでください。

入力の例

3 3
AD AU CL
HS GU HL
CS FD GS
1 2
BS BL
0 0

出力の例

Case 1
...
...
.F.
Case 2
..

追加入力1

上記Sampleの不足項目の検査（外側での連結、移動ルール、複数ペア）が目的。

1 3
BS AL BL
3 3
AR BS CD
FL FS FL
BU AL CL
0 0

追加出力1

Case 1
A..
Case 2
...
F..
...

出典

Shanghai 2004