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.
样例
3 3
...
.#.
...
4
3 5
...##
.#...
...#.
5
14 107
...........................................................................................................
...........................................................................................................
..#########..###....###########..###.......###...###########..####.......###...###########...###########...
..########..###....###########....###.....###...###########...#####......###..###########...###########....
..#######..###.....###.............###...###....###...........######.....###..###...........###............
..######..###......###..............###.###.....###...........###.###....###..###...........###............
..#####..###.......############......#####......############..###..###...###..###...........############...
..####....###......############.......###.......############..###...###..###..###...........############...
..###......###.....###................###.......###...........###....###.###..###...........###............
..##........###....###................###.......###...........###.....######..###...........###............
..#..........###...############.......###.......############..###......#####..############..############...
..............###...###########.......###........###########..###.......####...###########...###########...
...........................................................................................................
...........................................................................................................
91
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。