22518번 - Scribbling witch 다국어

문제

落書きの魔女 ALBERTINE は W 列 H 行の正方形のセルからなる長方形の結界の入り口に落書きをしている.この世界では落書きは必ずセルを白色か黒色で塗ることによって成り立つ.

すでに使い魔 ANJA の手によって落書きの一部が描かれているのだが,落書きの魔女は残りすべてのセルを塗り落書きを完成させたい.落書きの魔女にはあるこだわりがある.そのこだわりとは次のようなものである.

• 2 つの異なるセルが辺を共有するとき,2 つのセルは隣接していると呼ぶことにする.完成された落書きにおいては,任意の 2 つの黒いセルについて,片方からもう片方への隣接した黒いセルをたどるパスがちょうど 1 つだけ存在していなければならない.
• どの 2 つの白色のセルも隣接してはならない.

また,落書きの魔女は黒色が好きなので,こだわりを満たした状態でなおかつ最も黒色のセルが多い落書きを完成させたい.果たして落書きの魔女は最大で何個のセルが黒色に塗られたこだわりの落書きを描くことができるだろうか.

입력

入力は以下の形式で与えられる.

H W
c11c12…c1W
c21c22…c2W
…
cH1cH2…cHW

H は結界の入り口の縦幅,W は結界の入り口の横幅を表す.

c_ij は各セルの状態を表す文字であり,上から i 行目,左から j 列目のセルの状態を表す.セルに黒色が塗られている場合は c_ij は '#' となり,白色が塗られている場合は '.',まだ色が塗られていない場合はそうでない場合は '?' となる.

출력

魔女のこだわりを満たした状態でとりうる黒色のセルの個数の最大値を 1 行で出力せよ.

もしどのように塗っても魔女のこだわりを満たすように出来ない場合,-1 と出力せよ.

제한

• 1≤H≤11
• 1≤W≤11
• c_ij は '#', '.', '?' のいずれかである.

힌트