监控摄像头 3

题目描述

有一个从上到下 $H$ 行、从左到右 $W$ 列的网格。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

若 $S_{i,j}=$ #,则格子 $(i, j)$ 有障碍物;若 $S_{i,j}=$ .,则格子 $(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)$ 安装朝上和朝左的两个摄像头,即可监视所有无障碍物的格子。

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

5

例如,在格子 $(1, 1)$ 安装朝右和朝下的两个摄像头,在格子 $(3, 3)$ 安装一个朝左的摄像头,再在格子 $(2, 5)$ 安装朝左和朝下的两个摄像头,即可监视所有无障碍物的格子。

注意,格子 $(2, 5)$ 处朝左的摄像头无法监视格子 $(2, 1)$,因为中间隔着格子 $(2, 2)$ 上的障碍物。

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

91

数据范围

• $1 \le H,W \le 300$
• $S_{i,j}$ 是 . 或 #