Loading [MathJax]/extensions/tex2jax.js
比赛场次 210
比赛名称 20130729
比赛状态 已结束比赛成绩
开始时间 2013-07-29 08:30:00
结束时间 2013-07-29 11:30:00
开放分组 全部用户
注释介绍 2013B班二测
题目名称 激光电话
输入输出 lphone.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarSTARGAZER AAAAAAAAAA 0.006 s 0.37 MiB 100
Gravatar天下无敌 AAAAAAAAAA 0.012 s 0.33 MiB 100
GravatarCirno AAAAAAAAAA 0.014 s 0.37 MiB 100
Gravatar没饭了 饿死了 AAAWAAAAAA 0.241 s 0.32 MiB 90
Gravatar水木年华 WAEEWAAAEA 0.003 s 0.30 MiB 50
Gravatar/畅/ WAEEWAAAEA 0.005 s 0.30 MiB 50
Gravatarcuizhongyu WAEEWAAAEA 0.006 s 0.30 MiB 50
Gravatar隨風巽 AWWWWWAAWA 0.004 s 0.34 MiB 40
GravatarKZNS AWAWWWWWWW 0.005 s 0.31 MiB 20
Gravatar张汕成神犇 AWWWWWWWWW 0.001 s 0.16 MiB 10
Gravatarliu AWWWWWWWWW 0.002 s 0.17 MiB 10
Gravatarlmm AWWWWWWWWW 0.006 s 0.17 MiB 10
Gravatar5007 AWWWWWWWWW 0.007 s 0.15 MiB 10
Gravatar赵寒烨 AWWWWWWWWW 0.007 s 0.15 MiB 10
Gravatar李振文 ATTTTTTTTT 9.065 s 0.24 MiB 10
Gravatar我叫mt C 0.000 s 0.00 MiB 0
Gravatar郭垚池 C 0.000 s 0.00 MiB 0
GravatarLjt EEEEEEEEEE 0.001 s 0.55 MiB 0
Gravatar三木公98 WWWWWWWWWW 0.008 s 0.17 MiB 0
Gravatarraywzy EEEEEEEEEE 0.786 s 0.29 MiB 0
Gravatarhjh TTTTTTTTTT 10.011 s 0.17 MiB 0

激光电话

★☆   输入文件: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