D - ゆうびんやさんのお花畑

D - ゆうびんやさんのお花畑解説

実行時間制限: 5 sec / メモリ制限: 64 MB

あるところに妖精さんたちの住む村がありました。
図 1 は妖精さんの村の例です。妖精さんの村はマス目から成る長方形の形をしており、家と空き地と木で構成されています。

図 1：妖精さんの村の例

村には各妖精さんの家をまわって郵便配達をする妖精さん『ゆうびんやさん』がいます。
ゆうびんやさんには郵便配達のときに守らなければいけない以下の 5 つの規則があります。

例えばゆうびんやさんが配達に用いる経路の例を 1 つ挙げると図 2(a) のオレンジの線になります。
このとき、家は通り抜けてはいけない規則により図 2(b) のような配達経路は規則違反になります。

図 2(a)：配達経路の例　　　図 2(b)：規則違反の配達経路

さて、妖精さんたちはお花が大好きなので、ゆうびんやさんの配達経路以外の全ての空き地をお花畑にしたいと考えました。
その時のお花畑にできるマス目の個数の最大値を答えなさい。
なお、規則を守った配達経路が存在しない場合は -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(4≤H≤10) と東西の距離を表す整数 W(4≤W≤10) が空白を区切りとして与えられる。
2 行目からの H 行には、各行に妖精さんの村の各マス目の土地の利用状況を表す状態 c_{(i,j)}(0≤i≤W-1, 0≤j≤H−1) が W 文字ずつ与えられる。
- c_{(i,j)} は下記のいずれかであり、それぞれ西から i+1 番目の北から j+1 番目のマスの土地が何であるかを表す。
  - H : そのマスの土地に家があることを表す。
  - # : そのマスに木があることを表す。
  - . : そのマスが空き地であることを表す。
- 妖精さんの村に存在する家の総数は 3 以上 W×H 以下である。

妖精さんの村の大きさが小さい入力 (W=4, H=4) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

配達経路以外の空き地をお花畑にした場合のお花畑のマス目の個数の最大値を標準出力に 1 行で出力せよ。
ただし、規則を守った配達経路が存在しない場合は -1 を出力せよ。なお、最後には改行を出力せよ。

4 4
...H
#H..
...#
H..H

4 4
....
....
.HHH
....

4 4
...H
.#.#
.#.#
H#.H

修正：2012/08/29 19:40　右上のHが#になっている誤りがありましたので、修正させて頂きました。申し訳ありません。
なお、この修正によっての出力例への変更はありません。

4 4
HH.H
H##.
.##.
H..H

-1

10 10
..##.H....
.H.#......
...#####..
##......#.
.#...#.H..
.....#....
.##H..####
..##....H.
.H..#.....
...#......