配点 : $600$ 点

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。 マス $(i,j)$ は $S_{i,j}=$ # のとき障害物が置かれており、$S_{i,j}=$ . のとき何も置かれていません。

高橋君はグリッド内にいくつか監視カメラを設置しようとしています。

監視カメラは障害物のないマスに上下左右の $4$ 方向のいずれかの向きで置くことができます。 $1$ つのマスに複数台の監視カメラを設置することも可能です。

各監視カメラは、監視カメラの置かれたマス、及び、監視カメラの向いている向きにある直線上のマスを、障害物に遮られない範囲で監視することができます。

障害物の置かれていない全てのマスを監視するためには、最小でいくつの監視カメラを設置する必要がありますか？

制約

• $1 \leq H,W \leq 300$
• $S_{i,j}$ は . または # である

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$S_{1,1}\ldots S_{1,W}$

$\vdots$

$S_{H,1}\ldots S_{H,W}$

出力

答えを出力せよ。

3 3
...
.#.
...

4

例えば、マス $(1,1)$ に右向きと下向き、マス $(3,3)$ に上向きと左向きの合計 $4$ 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。

3 5
...##
.#...
...#.

5

例えば、マス $(1,1)$ に右向きと下向き、マス $(3,3)$ に左向き、マス $(2,5)$ に左向きと下向きの合計 $5$ 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。

マス $(2,5)$ に左向きに設置したカメラは、マス $(2,2)$ の障害物に遮られるため、マス $(2,1)$ を監視できないことに注意してください。

14 107
...........................................................................................................
...........................................................................................................
..#########..###....###########..###.......###...###########..####.......###...###########...###########...
..########..###....###########....###.....###...###########...#####......###..###########...###########....
..#######..###.....###.............###...###....###...........######.....###..###...........###............
..######..###......###..............###.###.....###...........###.###....###..###...........###............
..#####..###.......############......#####......############..###..###...###..###...........############...
..####....###......############.......###.......############..###...###..###..###...........############...
..###......###.....###................###.......###...........###....###.###..###...........###............
..##........###....###................###.......###...........###.....######..###...........###............
..#..........###...############.......###.......############..###......#####..############..############...
..............###...###########.......###........###########..###.......####...###########...###########...
...........................................................................................................
...........................................................................................................

91