Security Camera 3

题目描述

有一个从上到下 $H$ 行、从左到右 $W$ 列的格子。记位于从上数第 $i$ 行、从左数第 $j$ 列的格子为 $(i, j)$。
当 $S_{i,j}=$ # 时，格子 $(i, j)$ 被障碍物占据；当 $S_{i,j}=$ $.$ 时，该格子为空。 Takahashi 将在格子中安装一些监控摄像头。 监控摄像头可以放在没有障碍物的格子上，面向四个方向之一：上、下、左或右。
同一格子可以放置多台监控摄像头。 每台监控摄像头监视它所在的格子，以及它所面向方向上、直到遇到障碍物为止的格子。 至少需要多少台监控摄像头才能监视所有没有障碍物的格子？

输入格式

输入按照下列格式由标准输入提供： $H$ $W$ $S_{1,1}\ldots S_{1,W}$ $\vdots$ $S_{H,1}\ldots S_{H,W}$

输出格式

输出答案。

3 3
...
.#.
...

4

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

5

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

91

提示

$1 \leq H,W \leq 300$ $S_{i,j}$ 是 $.$ 或 #.例如，如果我们在格子 $(1, 1)$ 放置两台监控摄像头，分别朝右和朝下，并且在格子 $(3, 3)$ 放置另外两台分别朝上和朝左的摄像头，那么所有没有障碍物的格子都会被监视。
例如，如果我们在格子 $(1, 1)$ 放置两台监控摄像头，分别朝右和朝下，在格子 $(3, 3)$ 放置另一台朝左的摄像头，在格子 $(2, 5)$ 放置另外两台分别朝左和朝下的摄像头，那么所有没有障碍物的格子都会被监视。 注意位于格子 $(2, 5)$ 的朝左摄像头不能监视格子 $(2, 1)$，因为在格子 $(2, 2)$ 处有障碍物阻隔。

标签: AtCoder|abc274G

来源

AtCoder|abc274G