当前没有测试数据。

G - 安全摄像头 3

分数：600分

问题描述

给定一个由$H$行从上到下和$W$列从左到右组成的网格。用$(i, j)$表示第$i$行从上往下数，第$j$列从左往右数的方格。
如果方格$(i, j)$被障碍物占据，则$S_{i,j}=$ #，如果方格$(i, j)$为空，则$S_{i,j}=$ .。

高田会在网格中安装一些监控摄像头。

监控摄像头可以放置在没有障碍物的方格中，可以朝上、下、左或右四个方向中的一个方向放置。
可以在同一个方格中放置多个监控摄像头。

每个监控摄像头可以监控它所放置的方格及其朝向的方向，只要它们之间没有障碍物。

至少需要多少个监控摄像头才能监控所有没有障碍物的方格？

约束

• $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)$分别放置两个监控摄像头，并将它们朝右和朝下，再在方格$(1, 1)$和$(3, 3)$分别放置两个监控摄像头，并将它们朝上和朝左，那么所有没有障碍物的方格都将被监控到。

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

5

例如，如果我们在方格$(1, 1)$放置两个监控摄像头，并将它们分别朝右和朝下，再在方格$(3, 3)$放置一个监控摄像头，并将它朝左，最后在方格$(2, 5)$放置两个监控摄像头，并将它们分别朝左和朝下，那么所有没有障碍物的方格都将被监控到。

请注意，方格$(2, 5)$朝左的摄像头无法监控方格$(2, 1)$，因为其中间有一个障碍物在方格$(2, 2)$。

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

91