#P2937. [USACO09JAN] Laserphones S

    ID: 777 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>并查集广度优先搜索BFS最短路最近公共祖先LCA深度优先搜索DFSUSACO2009

[USACO09JAN] Laserphones S

题目描述

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:

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

题目大意

奶牛们都改用激光进行通讯了。

W×HW\times H 的牧场上,一些地方有树木和石头遮挡激光,所以,奶牛打算使用对角镜来进行激光通讯。两只奶牛的位置是固定的,对角镜能把光线旋转 9090 度。

下图是一个例子:

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!*! 表示障碍物,C\verb!C! 表示奶牛,/\verb!/!\\verb!\! 表示两种对角镜。

请求出最少需要安装的对角镜的数量,使得两只奶牛可以通讯。

7 8 
....... 
......C 
......* 
*****.* 
....*.. 
....*.. 
.C..*.. 
....... 

3