AT_tenka1_2012_12 ゆうびんやさんのお花畑

[problemUrl]: https://atcoder.jp/contests/tenka1-2012-qualC/tasks/tenka1_2012_12 あるところに妖精さんたちの住む村がありました。 図 $ 1 $ は妖精さんの村の例です。妖精さんの村はマス目から成る長方形の形をしており、家と空き地と木で構成されています。 図 $ 1 $：妖精さんの村の例 村には各妖精さんの家をまわって郵便配達をする妖精さん『ゆうびんやさん』がいます。 ゆうびんやさんには郵便配達のときに守らなければいけない以下の $ 5 $ つの規則があります。 1. 村にある全ての家に入って郵便を届けなければならない。 2. 木はよけなければならなく、空き地と家のみ通ってよい。また村の外は通ってはいけない。 3. 配達する時に通る空き地は何度同じ場所を通ってもよい。 4. 隣接した東西南北 $ 4 $ 方向のうち空き地である場所からのみ家に入らなければならない。 5. 家への出入りは $ 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\

N/A

N/A