D - ゆうびんやさんのお花畑
Editorial
/ 
入力は以下の形式で標準入力から与えられる。
妖精さんの村の大きさが小さい入力 (W=4, H=4) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。
配達経路以外の空き地をお花畑にした場合のお花畑のマス目の個数の最大値を標準出力に 1 行で出力せよ。
ただし、規則を守った配達経路が存在しない場合は
/ 
Time Limit: 5 sec / Memory Limit: 64 MB
問題文
あるところに妖精さんたちの住む村がありました。
図 1 は妖精さんの村の例です。妖精さんの村はマス目から成る長方形の形をしており、家と空き地と木で構成されています。
図 1：妖精さんの村の例
村には各妖精さんの家をまわって郵便配達をする妖精さん『ゆうびんやさん』がいます。
ゆうびんやさんには郵便配達のときに守らなければいけない以下の 5 つの規則があります。
- 村にある全ての家に入って郵便を届けなければならない。
- 木はよけなければならなく、空き地と家のみ通ってよい。また村の外は通ってはいけない。
- 配達する時に通る空き地は何度同じ場所を通ってもよい。
- 隣接した東西南北 4 方向のうち空き地である場所からのみ家に入らなければならない。
- 家への出入りは 1 つの方向からのみ行わなくてはならない。つまり、家を通り抜けてはならない。
例えばゆうびんやさんが配達に用いる経路の例を 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 以下である。
- c_{(i,j)} は下記のいずれかであり、それぞれ西から i+1 番目の北から j+1 番目のマスの土地が何であるかを表す。
出力
出力
ただし、規則を守った配達経路が存在しない場合は
-1 を出力せよ。
なお、最後には改行を出力せよ。
入力例 1
4 4 ...H #H.. ...# H..H
出力例 1
5
- 下図のようにお花畑を作ると、配達経路は規則を守ることができ、お花畑は 5 個になります。
入力例 2
4 4 .... .... .HHH ....
出力例 2
10
- 家同士が隣接していても直接家と家を移動することはできません。
- したがって家に隣接する北側の空き地 3 つ、または南側の空き地 3 つには花を植えられないので、お花畑は最大で 10 個になります。
入力例 3
4 4 ...H .#.# .#.# H#.H
修正：2012/08/29 19:40 右上のHが#になっている誤りがありましたので、修正させて頂きました。申し訳ありません。
なお、この修正によっての出力例への変更はありません。
なお、この修正によっての出力例への変更はありません。
出力例 3
0
- 全ての空き地が配達経路上にあるので、お花畑は作ることができません。
入力例 4
4 4 HH.H H##. .##. H..H
出力例 4
-1
- 北から 1 番目で西から 1 番目のマスにある家には配達できないことや、家を通り抜けないと配達できないことから、配達規則を守ることができません。
入力例 5
10 10 ..##.H.... .H.#...... ...#####.. ##......#. .#...#.H.. .....#.... .##H..#### ..##....H. .H..#..... ...#......
出力例 5
36