|
|
赛题二：智能交通
下图所示为为一个十字路口，在十字路口的各个方向上有一些汽车正准备经过十字路口达到目的地。现需要根据机车当前所处的位置和它们的目的地来合理的安排十字路口的红绿灯的显示时间，使所有的机车能够在尽可能短的时间内达到目的地。
… …
N(1,3) N(2,3)
N(1,2) N(2,2)
N(1,1) N(2,1)
… W(2,3) W(2,2) W(2,1) C3 C2 E(1,1) E(1,2) E(1,3) …
… W(1,3) W(1,2) W(1,1) C4 C1 E(2,1) E(2,2) E(2,3) …
S(2,1) S(1,1)
S(2,2) S(1,2)
S(2,3) S(1,3)
… …
图示说明
（1） 蓝色区域表示公路，黄色区域表示十字路口。
（2） 坐标说明：E(1,2) E表示坐标点位于十字路口的方向，1表示该点为右侧，
2表示该坐标点的在此方向上的位移； W(2,3) W表示方向；2表示该点左侧点；3表示该点在此方向上位移；右侧点和左侧点都以面向十字路口为基准。
（3） 汽车的初始位置只能是右侧点，目的地只能是左侧点。
（4） 汽车的经过十字路口后可直行、右拐、左拐
（5） E 表示十字路口的东方向；N 表示十字路口的北方向；W 表示十字路口的
西方向；S 表示十字路口的南方向。
题目说明
（1） 一辆汽车在占一格，同一时间内，一个格子只题目说明能有一辆汽车。
（2） 汽车的速度相同，一个时间单位内只能走一格。
（3） 汽车只能沿直线行进，不可以走斜线，如E(1,1) 处的汽车需要左拐，必须
经过C2、C3、C4、S(2,1)
（4） 汽车的行进路线中不允许出现环形。
（5） 汽车在左拐时要按照逆时针的方向行进。如：S(1,1)车汽车左拐经过C1、
C2、C3而不是C1、C4、C3。
（6） 和实际情况一样，汽车必须遵循右侧通行准则。
（7） 汽车到达目的地后就当作消失。此格其它汽车可以使用。
（8） 汽车的目的地可能相同。
（9） 右拐汽车在十字路口不需要等待信号灯。
（10）汽车的行进方向由起点和终点坐标判断。
（11）信号灯每次显示的时间为15－30个时间单位
（12）初始时十字路口信号灯状态自定。
（13）输入、输出文件的示例只是格式示例。
题目要求
（1） 当所有车辆的前进方向均为直线时（既不存在左拐或者右拐的汽车），设计
十字路口信号灯的显示方案,使所有汽车达都达到目的地所需的时间最短。
（2） 汽车的行进方向不定，给出一种信号灯显示的较优方案,使所有汽车到达目
的地所需的时间尽可能短。
输入文件格式
第1行：n：表示汽车总量。第2行开始至第N＋1行表示n辆车的起点和终点。第一列为起点的方向坐标；第二列表示为右侧（均为1）；第三列为起点在方向上的位移；第四列为目的地的方向；第五列表示左侧目的地（均为2）第六列为目的地在方向上的位移。各列之间用空格符分隔。
如下所示：
第1行 5
第2行 S 1 3 W 2 4
第3行 W 1 2 E 2 2
第4行 W 1 5 N 2 6
第5行 N 1 8 S 2 7
第6行 E 1 4 S 2 7
输出文件格式
输出文件包括两个文件：第一个保存信号灯信息：第一列为信号灯显示序号（1，2，3，…)第二列为当前绿灯方向（NS：表示南北、EW表示东西）第三列为绿灯显示时间 n个时间单位各列之间以空格间隔最后一行显示共用时间。如下所示：
1 NS 17
2 EW 15
3 NS 18
4 EW 20
5 NS 16
… … …
180
第二个文件要求保存每一个时间内，没有到达目的地的车的位置。第1行为当前单位时间内没有到达目的地的车的数目 m。第2行至第m＋1行表示车的当前位置。各列要求与输入文件格式相同，各列之间用空格分隔。第m＋2行为下一个时间单位没有到达目的地的车的数目。依此类推，直到最后一个时间单位，所有车都到达目的地最后一行显示0，如下所示：
3
S 1 3 W 2 3
W 1 8 W 1 1
E 1 1 S 2 4
1
W 1 8 C 1 2
1
W 1 8 C 1 1
1
W 1 8 E 2 1
0
|
|
发表于 2004-3-28 01:16:20