2004db

Problem B: Red and Black 赤と黒

赤いタイルと黒いタイルが強いてある部屋で、隣接している黒いタイルだけ移動できる。このとき、最初の位置から移動できるタイルの枚数を数える問題。

入力

• まず部屋の大きさW(横)とH(縦)。2つとも0だったら終了する。
• 続いて文字の入力。．(ドット)が黒いタイル(移動できる場所)、＃が赤いタイル(移動できない場所)、＠が最初の位置を表す。

出力

• 最初の位置から到達可能なタイルの数を表示。

データ構造

2次元配列で部屋を表現する。文字2次元配列でも解けると思うが、整数型にしてしまったほうが考えやすいかも。黒いタイルを0、赤いタイルを1などとして。

解答例

• 方法1：再帰でバックトラックのやり方が分かれば、解けるかな。
  • 2004db1.c
• 方法2：再帰を使わなくても作れる。部屋の広さが大きいときは時間がかかるかも。
  • C 2004db2.c
  • Java randb.java