网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Jan09]激光电话
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | lphone.in | 输出文件 | lphone.out |
奶牛们有了一套新的激光系统,这使它们在牧场的时候可以随心所欲地进行交谈,它们的牧场被设计为由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