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