Score : $600$ points

问题陈述

存在一个从上到下有 $H$ 行、从左到右有 $W$ 列的网格。令 $(i, j)$ 表示从顶部数第 $i$ 行、从左边数第 $j$ 列的方格。

若 $S_{i,j}=$ #，则表示方格 $(i, j)$ 被障碍物占据；若 $S_{i,j}=$ .，则表示该方格为空。

高桥将在网格中安装一些监控摄像头。

监控摄像头可以放置在没有障碍物的方格上，并且可以选择四个方向之一进行安装：向上、向下、向左或向右。 多个监控摄像头可以放置在同一方格上。

每个监控摄像头会监视其所在方格及其所朝向的所有连续方格（只要其间无任何障碍物阻挡）。

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

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:33:28