No.348 カゴメカゴメ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : motimoti

3 ProblemId : 795 / 出題時の順位表

問題文

$N×M$のグリッドがある。各マスは'.'と'x'で構成される。2つの'x'がマスの頂点を共有するとき、それらは「連なる」という。
また、'x'を8近傍で繋いで3マス以上の閉路が構成できるとき、輪であるとする。

どの'x'も、必ず別のちょうど2つの'x'と連なって輪を作っている。輪ごとに強さがあり、構成している'x'の数で定義される。

各々の輪について、「使用する」か「使用しない」かを選ぶことが出来る。使用する輪の強さの合計が、グリッドの強さとなる。
ある輪と、その輪のすぐ外側にある輪の両方を使用することは出来ない。

例えば以下の図において使用する輪を赤色、使用しない輪を青色に塗り替える。




このとき、以下の5通りの使用が許される。



使用する輪を適切に選んだとき、グリッドの強さの最大値を求めよ。

入力

$N$ $M$
$grid_0$
$grid_1$
...
$grid_{N-1}$

  • $1 ≤ N, M ≤ 10^3$
  • $grid_i$ $(0 ≤ i ≤ N-1)$ は、要素数が $M$ であり、 '.' と 'x' のみで構成される文字列である。
  • 各「連なり」は一意的な輪が構成できることが保証される(複数の輪が解釈できることはないとして良い)
  • 輪を構成しない'x'はない

出力

グリッドの強さの最大値を出力せよ。

サンプル

サンプル1
入力
5 10
..........
..xx...xx.
.x..x.x..x
..xx...xx.
..........
出力
12

2つの輪は互いに囲まれていない。それぞれの輪の強さは6であり、グリッドの強さは12である。

サンプル2
入力
2 2
xx
x.
出力
3

ある'x'は、必ず他のちょうど2つの'x'と連なって、一つの輪を構成している。

サンプル3
入力
1 1
.
出力
0

輪が一つも存在しない。

サンプル4
入力
12 23
..xxxxxxxxxxxxxxxxxxxx.
.x....................x
.x..xxxxxx...xxxxxxx..x
.x.x......x.x.......x.x
.x.x..xx..x.x..xx...x.x
.x.x.x..x.x.x.x..x..x.x
.x.x..xx..x.x.x..x.x..x
.x.x......x.x..xx..x..x
.x..xxxxxx...x....x...x
.x............xxxx....x
.x....................x
..xxxxxxxxxxxxxxxxxxxx.
出力
74


使用する輪を赤色、使用しない輪を青色に塗ったときの図が以下あたる。

提出ページヘ