题目名称	524. [USACO Jan09] 激光电话
输入输出	`lphone.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2010-12-24加入
开放分组	全部用户
提交状态
分类标签	搜索法动态规划 USACO
	分享题解

通过：96，提交：208，通过率：46.15%
521	100	0.000 s	0.00 MiB	C++
dateri	100	0.000 s	0.00 MiB	C++
Regnig Etalsnart	100	0.000 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.000 s	0.00 MiB	C++
宇战	100	0.000 s	0.00 MiB	C++
小金	100	0.000 s	0.00 MiB	C++
老师好~~~	100	0.003 s	0.36 MiB	C++
wolf	100	0.003 s	0.37 MiB	C++
努力吧	100	0.004 s	0.33 MiB	C++
chs	100	0.004 s	0.35 MiB	C++

本题关联比赛
20101224
20130729
20130729
动态规划练习赛1102

关于激光电话的近10条评论(全部评论)
靠 521 2016-05-01 19:58 11楼
forever 2015-06-15 18:42 10楼
苜 2014-10-25 16:36 9楼
这个BFS非常朴素~ 筽邝 2014-10-15 21:17 8楼
mark Ezio 2014-10-15 21:16 7楼
仅供参考的代码,不要吐槽奇葩的变量名: 水中音 2014-10-08 19:39 6楼
行和列打反了。。。。 HouJikan 2014-09-19 16:42 5楼
回复 @水中音AiKy : 在评论框选中"允许查看你提交的代码"即可让别人看代码，不必贴出来占版面 cstdio 2014-08-27 11:20 4楼
这个BFS非常酷炫~ digital-T 2013-11-02 11:31 3楼
擦擦擦....完全用宽搜做这道题最多过9个点（跟数据有关，本人亲测）。。。四种不同的方向打乱顺序后会有覆盖= =.... 老师好~~~ 2013-08-05 17:01 2楼

524. [USACO Jan09] 激光电话

★☆ 输入文件：lphone.in 输出文件：lphone.out 简单对比
时间限制：1 s 内存限制：128 MiB

奶牛们有了一套新的激光系统，这使它们在牧场的时候可以随心所欲地进行交谈，它们的牧场被设计为由W*H个点组成的网格。（1 <= W <= 100; 1 <= H <= 100）
这套系统要求类似视线连通以确保维持通讯，当然了，牧场里还有一些石头和树，这些东西会干扰通讯，但是奶牛们早有准备，它们购买了一些斜放的反光镜（如下图中的"/"和"\"），它些镜子能通过反射把激光束扭转90度，下面是问题的一个图解。
在这个地图中H=8，W=7，两头正在通讯的奶牛用符号"C"表示，石头及其它障碍物用"*"表示：

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表示），才能保证这两头牛之间的激光通讯，注意所给的数据一定有解。
程序名：lphone
输入格式：
第1行有两个空格隔开的整数：W,H；
第2～H+1行为完整的牧场。
输出格式：
一行，一个整数M，即反光镜的个数。
输入样例(lphone.in)
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

输出样例(lphone.out)
3