Filling Game

Time Limit : 3 sec, Memory Limit : 65536 KB

塗りつぶしゲーム

指で画面にタッチして操作できる、直感的なタブレットインターフェースの技術は、ゲームの分野でも応用され、新しい操作感を持つ様々な種類のゲームが作られています。現在、AZ社が開発しているゲームもその一つです。

このソフトウェア(ゲーム)の要件は以下の通りです。

  • 画面にはx列×y行の2次元グリッドがあります。
  • グリッドのセルは赤(R)、緑(G)、茶(B)の3色のいずれかで塗られています。
  • セルの色を変更するボタンR、G、Bがあり、このボタンが押下されると一番左上(0,0)のセルがその色に変更されます。
  • 一番左上のセルの色が変更されると、そのセルの元の色と同じ色に塗られた隣接するすべてのセルが指定された色に変わります。すなわち、元の色が同じ色のセルでつながったセルはすべて指定された色に変更されます。

このようにグリッドを塗りつぶしていき、最終的にグリッド全体を一色にするというゲームです。少ない手順で解くと高得点が与えられます。

AZ社のプログラマーであるあなたは、このゲームのロジックの一部分を開発することになりました。まずは、この最高得点を計算するため、このゲームを最短で解いた場合、最低何回選択ボタンを操作すればグリッドが一色になるかをもとめるプログラムを作ることにしました。

2次元のグリッドのサイズx×yと各セルの初期状態の色(R、G、Bのいずれか)を入力とし、すべてのセルを同一色にするために必要な選択ボタンの操作回数の最小値を出力するプログラムを作成してください。ただし、xとyは2以上10以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつで示されます。

1行目 x y(整数 整数;半角空白区切り)
2行目 1行目のセルの色s1 … sx(すべて半角英字;半角空白区切り)

y+1行目 y行目のセルの色

出力

入力データセットごとに、ボタン操作の最少回数を出力します。

入力例

3 3
R G B
G G G
G B B
2 4
R G
G G
R B
B R
4 3
G G B R
G R R G
B G G R
0 0

出力例

2
4
4

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/