102746: [AtCoder]ABC274 G - Security Camera 3

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

问题描述

有一个从上到下有$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
...##