D - 大爆発
Editorial
/ 
入力は以下の形式で標準入力から与えられる。
ステージのサイズが小さい入力 (1≤W≤5, 1≤H≤5) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。
ステージ上にブロックが 1 つも存在しない状態にするために必要な爆弾の個数を標準出力に 1 行で出力せよ。
また、ステージ上にブロックが存在しない状態にすることができない場合は
なお、行の終端には改行が必要である。
/ 
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
マス目から成るステージが与えられ、そのステージに存在するブロックを爆弾を用いて全て壊すゲームを行います。
爆弾はブロックのないマスにのみ置くことができ、爆弾は置くとすぐに爆発し上下左右全てのブロックを破壊します。
例えば、図 1 のようなステージで座標 (1,3) に爆弾を置くと、上下左右 5 つのブロックを破壊することができます。
以降の座標とはステージの左上のマスを (0,0) とし、1 つ右のマスを (1,0)、1 つ下のマスを (0,1) とします。
この際、図 1 における爆弾上部のブロックのように爆弾とブロックが隣接していなくても破壊され、ブロックがいくつ連続していても全て破壊されます。
また、爆弾右部のブロックのように各ブロックが隣接していなくても全て破壊されます。
図 1 : 爆弾がブロックを破壊する例
ステージ上にある全てのブロックを破壊するために必要な爆弾の個数を答えなさい。
また、全てのブロックを破壊することが不可能な場合は -1 と出力しなさい。
入力
H W
c_{(0,0)}c_{(1,0)}‥‥c_{(W-1,0)}
c_{(0,1)}c_{(1,1)}‥‥c_{(W-1,1)}
:
:
c_{(0,H-1)}c_{(1,H-1)}‥‥c_{(W-1,H-1)}
- 入力は H+1 行ある。
- 1 行目には、与えられるステージの縦の長さを表す整数 H(1≤H≤16) と 横の長さを表す整数 W(1≤W≤16) が空白を区切りとして与えられる。
- 2 行目からの H 行には、各行にステージの各マス目に対するブロックの有無を表す状態 c_{(i,j)}(0≤i≤W-1, 0≤j≤H−1) が W 文字ずつ与えられる。
- c_{(i,j)} は下記のどちらかであり、それぞれ座標 (i,j) のマスが下記のような状態であることを表す。
.: そのマスにブロックが無いことを表し、そのマスには爆弾を置くことができる。#: そのマスにブロックがあることを表し、そのマスには爆弾を置くことができない。
- c_{(i,j)} は下記のどちらかであり、それぞれ座標 (i,j) のマスが下記のような状態であることを表す。
部分点
出力
また、ステージ上にブロックが存在しない状態にすることができない場合は
-1 と出力せよ。なお、行の終端には改行が必要である。
入力例 1
5 5 .#.#. .#... ...#. #.#.# #...#
出力例 1
2
- 初期位置は図 1 が示す形なので、まず座標 (1,3) に爆弾を置くと座標 (0,3), (1,0), (1,1), (2,3), (4,3) のブロックを破壊することができます。
- 次に座標 (3,4) の位置に爆弾を置くことで、残りのブロックを全て破壊できます。
- したがって、ブロックを全て破壊するために必要な爆弾の個数は 2 個となります。
入力例 2
5 5 .#... .#... ##### .#... .#...
出力例 2
3
- まず、座標 (0,1) に爆弾を置き、(0,2) と (1,1) のブロックを破壊します。
- 次に、座標 (1,1) に爆弾を置き、(1,0), (1,2), (1,3), (1,4) のブロックを破壊します。
- 最後に、座標 (1,2) に爆弾を置くことで、残りのブロックを全て破壊することができます。
- したがって、ブロックを全て破壊するために必要な爆弾の個数は 3 個となります。
入力例 3
1 6 ######
出力例 3
-1
- どのマスにも爆弾を置くことができないので、ブロックを破壊することができません。
入力例 4
3 2 .. .. ..
出力例 4
0
- 与えられた時点でブロックが存在しない状態なので、爆弾は必要ありません。