P2937 [USACO09JAN] Laserphones S
题目描述
奶牛们有一个新的激光系统，这样它们在牧场上时可以进行随意的交谈。牧场被建模为一个 $W \times H$ 的点阵（$1 \leq W \leq 100$，$1 \leq H \leq 100$）。
该系统需要某种视线连通性以维持通信。当然，牧场上有岩石和树木会干扰通信，但奶牛们购买了对角镜（如下的 '/' 和 '\\'）来使激光束偏转 90 度。下面是一个说明问题的地图。
对于这张地图，$H$ 是 8，$W$ 是 7。两个正在通信的奶牛用 'C' 表示；岩石和其他阻挡元素用 '*' 表示：
```plain
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6
```
确定必须安装的最少镜子数量 $M$，以维持两头奶牛之间的激光通信。在给定的测试数据中，这一壮举总是可能的。
输入格式
\* 第 1 行：两个用空格分隔的整数：$W$ 和 $H$
\* 第 2 行到第 $H+1$ 行：整个牧场。
输出格式
\* 第 1 行：一个整数：$M$
说明/提示
（由 ChatGPT 4o 翻译）