AT_tenka1_2012_8 大爆発

[problemUrl]: https://atcoder.jp/contests/tenka1-2012-qualB/tasks/tenka1_2012_8 マス目から成るステージが与えられ、そのステージに存在するブロックを爆弾を用いて全て壊すゲームを行います。 爆弾はブロックのないマスにのみ置くことができ、爆弾は置くとすぐに爆発し上下左右全てのブロックを破壊します。 例えば、図 $ 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\

N/A

N/A