102746: [AtCoder]ABC274 G - Security Camera 3
Description
Score : $600$ points
Problem Statement
There is a grid with $H$ rows from top to bottom and $W$ columns from left to right. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.
Square $(i, j)$ is occupied by an obstacle if $S_{i,j}=$ #, and is empty if $S_{i,j}=$ ..
Takahashi will install some surveillance cameras in the grid.
A surveillance camera can be placed at a square without an obstacle, in one of the four directions: up, down, left, or right.
Multiple surveillance cameras may be placed at the same square.
Each surveillance camera monitors the square it is placed at, and the squares in the direction it is placed in, as far as there is no obstacle in between.
At least how many surveillance cameras are needed to monitor all squares without an obstacle?
Constraints
- $1 \leq H,W \leq 300$
- $S_{i,j}$ is
.or#.
Input
The input is given from Standard Input in the following format:
$H$ $W$
$S_{1,1}\ldots S_{1,W}$
$\vdots$
$S_{H,1}\ldots S_{H,W}$
Output
Print the answer.
Sample Input 1
3 3 ... .#. ...
Sample Output 1
4
For example, if we install two surveillance cameras at square $(1, 1)$ facing right and down, and another two at square $(3, 3)$ facing up and left, all squares without an obstacle will be monitored.
Sample Input 2
3 5 ...## .#... ...#.
Sample Output 2
5
For example, if we install two surveillance cameras at square $(1, 1)$ facing right and down, another at square $(3, 3)$ facing left, and another two at square $(2, 5)$ facing left and down, all squares without an obstacle will be monitored.
Note that the camera at square $(2, 5)$ facing left cannot monitor square $(2, 1)$, since there is an obstacle in between at square $(2, 2)$.
Sample Input 3
14 107 ........................................................................................................... ........................................................................................................... ..#########..###....###########..###.......###...###########..####.......###...###########...###########... ..########..###....###########....###.....###...###########...#####......###..###########...###########.... ..#######..###.....###.............###...###....###...........######.....###..###...........###............ ..######..###......###..............###.###.....###...........###.###....###..###...........###............ ..#####..###.......############......#####......############..###..###...###..###...........############... ..####....###......############.......###.......############..###...###..###..###...........############... ..###......###.....###................###.......###...........###....###.###..###...........###............ ..##........###....###................###.......###...........###.....######..###...........###............ ..#..........###...############.......###.......############..###......#####..############..############... ..............###...###########.......###........###########..###.......####...###########...###########... ........................................................................................................... ...........................................................................................................
Sample Output 3
91
Input
题意翻译
给定一张 $H$ 行 $W$ 列的网格图。设 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置，其中的字符 `.` 表示空白，`#` 表示障碍。 你可以在空白的位置放监控摄像头。监控有四个方向：前后左右。一个方向的监控只能看到自己正方向的位置。例如，向前的监控只能看到自己正前方的位置。 监控的视野会被障碍挡住。一个位置可以放多个监控。你需要求出最少的放置数量，使得所有的空白位置都能被看到。 $1\le H,W\le 300$。Output
问题描述
有一个从上到下有$H$行、从左到右有$W$列的网格。用$(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}$
输出
打印答案。
样例输入1
3 3 ... .#. ...
样例输出1
4
例如，如果我们在格子$(1, 1)$上安装两个朝右和朝下的监控摄像头，在格子$(3, 3)$上安装两个朝上和朝左的监控摄像头，那么所有没有障碍物的格子都将被监视。
样例输入2
3 5 ...##