AT_abc274_g [ABC274G] Security Camera 3

题目描述

有一个高为 $H$、宽为 $W$ 的网格。第 $i$ 行第 $j$ 列的格子记作格子 $(i,j)$。
当 $S_{i,j}=$ # 时，格子上有障碍物；当 $S_{i,j}=$ . 时，格子上没有任何东西。

高桥君打算在网格中安装若干台监视摄像头。

监视摄像头只能放在没有障碍物的格子上，并且可以朝上下左右四个方向中的任意一个方向放置。
同一个格子上可以放置多台监视摄像头。

每台摄像头可以监视其所在的格子，以及其朝向方向上、在没有被障碍物阻挡的直线上所有格子。

要想监视所有没有障碍物的格子，最少需要安装多少台监视摄像头？

输入格式

输入按以下格式从标准输入读入。

$H$ $W$
$S_{1,1}\ldots S_{1,W}$
$\vdots$
$S_{H,1}\ldots S_{H,W}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3
...
.#.
...

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

5

输入输出样例 #3

输入 #3

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

输出 #3

91

说明/提示

限制条件

• $1 \leq H, W \leq 300$
• $S_{i,j}$ 仅为 . 或 #

样例解释 1

例如，在格子 $(1,1)$ 放置一台朝右、一台朝下的摄像头，在格子 $(3,3)$ 放置一台朝上、一台朝左的摄像头，共计 $4$ 台摄像头，就可以监视所有没有障碍物的格子。

样例解释 2

例如，在格子 $(1,1)$ 放置一台朝右、一台朝下的摄像头，在格子 $(3,3)$ 放置一台朝左的摄像头，在格子 $(2,5)$ 放置一台朝左和一台朝下的摄像头，共计 $5$ 台摄像头，就可以监视所有没有障碍物的格子。需要注意的是，放在 $(2,5)$ 的朝左摄像头会被 $(2,2)$ 的障碍物阻挡，无法监视到 $(2,1)$。

由 ChatGPT 4.1 翻译