AT_abc274_g.[ABC274G] Security Camera 3

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个高为 $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
```
3 3
...
.#.
...
```
输出#1
```
4
```
输入#2
```
3 5
...##
.#...
...#.
```
输出#2
```
5
```

输入#3

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

输出#3

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页