题目描述

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

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

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

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

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

给定一张 $H$ 行 $W$ 列的网格图。设 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置，其中的字符 . 表示空白，# 表示障碍。

你可以在空白的位置放监控摄像头。监控有四个方向：前后左右。一个方向的监控只能看到自己正方向的位置。例如，向前的监控只能看到自己正前方的位置。

监控的视野会被障碍挡住。一个位置可以放多个监控。你需要求出最少的放置数量，使得所有的空白位置都能被看到。

$1\le H,W\le 300$。

3 3
...
.#.
...

4

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

5

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

91

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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