[USACO09JAN] Laserphones S
题意翻译
奶牛们都改用激光进行通讯了。
在 $W\times H$ 的牧场上,一些地方有树木和石头遮挡激光,所以,奶牛打算使用对角镜来进行激光通讯。两只奶牛的位置是固定的,对角镜能把光线旋转 $90$ 度。
下图是一个例子:
```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
```
其中 $\verb!*!$ 表示障碍物,$\verb!C!$ 表示奶牛,$\verb!/!$ 和 $\verb!\!$ 表示两种对角镜。
请求出最少需要安装的对角镜的数量,使得两只奶牛可以通讯。
题目描述
The cows have a new laser-based system so they can have casual conversations while out in the pasture which is modeled as a W x H grid of points (1 <= W <= 100; 1 <= H <= 100).
The system requires a sort of line-of-sight connectivity in order to sustain communication. The pasture, of course, has rocks and trees that disrupt the communication but the cows have purchased diagonal mirrors ('/' and '\' below) that deflect the laser beam through a 90 degree turn. Below is a map that illustrates the
problem.
H is 8 and W is 7 for this map. The two communicating cows are notated as 'C's; rocks and other blocking elements are notated as '\*'s:
```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
```
Determine the minimum number of mirrors M that must be installed to maintain laser communication between the two cows, a feat which is always possible in the given test data.
输入输出格式
输入格式
\* Line 1: Two space separated integers: W and H
\* Lines 2..H+1: The entire pasture.
输出格式
\* Line 1: A single integer: M
输入输出样例
输入样例 #1
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......
输出样例 #1
3