仓库路线设计

 

  ●问题描述

  ACK是一家以生产计算机及其外设产品为主的高科技企业。不仅ACK的产品在国内领先,而且它的仓库设计也独具特色。由于生产的产品多种多样,ACK的仓库是由若干个大小不等、形状各异的子仓库组成,每个仓库有一个入口(也是出口),坐标为。由于有些产品是互相关联的,所以某些仓库的入口之间通过地下通道相联。(0,0)是地下通道的入口处。每次装卸货物时,仓库的运输车都要从(0,0)处进入地下通道,在通道中行驶一段距离后进入到某一子仓库中装卸货物。但是最近运输车出现了一点小毛病,那就是运输车只能右转弯,而不能左转弯。这对运输车在仓库中运输货物并没有什么影响,但是由于地下通道的宽度有限,运输车转弯的角度不能超过180。在这种情况下,某些仓库仍然是可到达的,但是有些仓库却是根本不能到达的。例如在如上图)。

  例子中,如果运输车的行驶路线为O-B-D-E-F-B-A(这条路线保证了运输车不进行左转弯),则可依次到达子仓库B、D、E、F、A,但是无论运输车如何选择其他的路线,子仓库C都是不能到达的。

  作为ACK的高级工程师,请你编程找出从O点可以到达的所有子仓库。

  注意:为保持仓库的清洁,地下通道采用"管道"的形式(除入口和出口以外都是封闭的),所以即使仓库i和仓库j相连,仓库k的坐标为的连线上,当运输车在从仓库i到仓库j的路线上时仍不能到达仓库k。

  ●数据输入:输入数据由line.in提供。文件的第一行为一个整数N(N≤200),表示共有N个子仓库。从第二行开始到第(N+1)行每行有两个数(-50≤xi,yi≤50),表示第i个仓库的坐标。然后是一个整数M(M≤100),表示共有M条路线。接下来的M行每行有两个整数P、Q,表示子仓库P和子仓库Q有通道相连,在这里通道是双向的,即如果P可以和Q相连,那么Q也一定和P相连。其中仓库的入口(0,0)用0表示。

  ●结果输出:将可能到达的子仓库序号按升序输出到文件line.out中。输入文件中给出的数据保证至少有一个可达子仓库。

  ●输入输出样例

输入文件样例 输出文件样例
line.in line.out
6
0 4
1 2
2 4
2 3
3 2
2 1
8
0 2
1 2
1 4
2 4
3 4
4 5
5 6
2 6
1 2 4 5 6














 

 
 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有