首页 > 代码库 > 海康威视复赛题
海康威视复赛题
题目概述
在车库中安排若干泊车机器人，根据给定的车位地图，合理优化机器人的数量及其运动路径，尽量减少客户在停车和取车中的等待时间，并使总成本最小。
参数设定
为了简化问题，我们对泊车机器人的实际运行情况做出如下规定和说明，与“题目背景”中所述的泊车机器人真实运行情况有所不同，请注意。
地图说明：
给定一个停车地图，以下图为例：地图中红色部分表示车位（P），黑色部分表示障碍物（B），黄色部分表示入口（I），绿色部分表示出口（E），白色表示行车道路（X），每个车位都与行车道路（X）相邻，每个车位（P）只能停一辆车。
1.泊车机器人必须能到达每个车位；
2.每个车位有且只有一个入口, 即每个红色区域旁边有且只有一个白色区域；
3.出口和入口各只有一个，且不重合，分布在地图边缘，泊车机器人从入口和出口都能到达每个车位。
泊车机器人说明：
1.泊车机器人（R）运行速度为每秒一个格，且只能向前、后、左、右移动，不能沿对角线移动。
2.泊车机器人不论在载车还是空车状态，都不能穿过图例中黑色区域（B）；且只能由白色区域（X）进入到红色区域（P），或相反；不能在红色区域（P）之间移动。比如，上图图例中左上角， 允许3->1和1->3，但不允许1->2。
3.泊车机器人在空闲的时候，可以行驶到任何位置（除了B区域）。
4.泊车机器人不论是空车还是载车状态都不能同时出现在一个格子中（入口和出口处不受限制），即不能相遇，不能相撞，存在碰撞体积。
5.假设泊车机器人空载时耗能极少可忽略不计，载车时能耗（W）与车的质量（m）以及行驶里程（S）相关，W=k*m*S，k为能耗系数。
车辆说明：
1.每辆车（C）都有申请进入时间（T-in）、申请离开时间(T-out)、实际进入时间（T-in＇）、实际离开时间（T-out＇）、最长等待时间（t）、车的质量（m，m≤2000）。
2.申请进入时间（T-in）表示车辆到达时间，实际进入时间（T-in＇）为泊车机器人从入口处把车辆接走的时间点；申请离开时间(T-out)表示客户取车的时间点，实际离开时间（T-out＇）表示泊车机器人把车辆搬到出口的时间点；若（T-in＇）＞（T-in）+（t），则客户放弃停车。
3.每辆车的等待时间（T1）=（T-in＇）-（T-in）+（T-out＇）-(T-out)；若发生客户放弃停车的情况，需要对每辆被放弃的车辆增加罚时（p），总罚时（T2）=罚时系数（p）*放弃停车车辆数（q）。（注：放弃停车的车辆的等待时间，不计算到T1，该车不会停到车库里面，因此也不用规划路径，只需要计入T2即可）
题目说明
现有一批车辆需要停到车库中，请设计一个合理的停车方案，使Z最小。 Z =a*n+T+W。
n为泊车机器人个数，a为系数；T=bT1+T2， b为系数；W为总能耗。具体公式为 Z = n*a + b*∑T1 + p*q + k*∑m*s
输入
1.从标准输入 输入的数据以空格分隔，每行以换行符（‘\n’）结尾。
2.格式：
能耗系数k 罚时系数p 泊车机器人系数a 客户停车等待系数b
停车库宽w 停车库高h
接下来是一个w*h的二维数组， 数组中P表示车位，B表示障碍物，I表示入口，E表示出口，X表示过道
车辆数目N
1 申请入库时间点 申请出库时间点 最大等待时间 车的质量
2
3
.
.
N 申请入库时间点 申请出库时间点 最大等待时间 车的质量
说明：
a.所有输入都是不小于0的整数，且不大于100000，地图宽高都不大于100，车辆数N不大于5000
b.为了方便计算，时间点都是归一化时间，即从0开始，依次增加
c.机器人行驶里程说明，例如示例图中车辆从入口4到停车位6，它的行驶路程为4->5->6,那么它的里程数为2
输入示例：
1 800 400 5 //能耗系数k:1， 罚时系数p:800， 泊车机器人系数a:400，等待系数b:5
6 6 // 地图宽高都为6
X X X X X X
X B P P P P
X X B B B B
X X X X X E
X X X X X X
I B P P B B
4 // 车辆数为4
1 0 42 20 10 // 车辆编号为1，申请进入时间点为0，申请离开时间点42，最大等地时间20，质量为10，即车辆如果在0+20这个时间点还没有被接走，就表示该车放弃泊车。
2 3 45 15 15
3 10 64 10 11
4 25 60 20 12
输出
1.标准输出，输出的数据以空格分隔，每行以换行符（‘\n’）结尾。
2.输出格式：
首先判断给的用例地图是否有效（判断依据见地图说明），
如果地图无效则：NO
文件结束
如果地图有效：YES
泊车机器人个数n 所有车的等待时间T（b*T1+T2） 所有泊车机器人的总能耗W处理完当前case所用的经历时间M(指最后一辆车离开车库的时间，相当于这个时间点后，没有车入库了，程序运行结束)
接下来M +1行，
0 (机器人编号0，当前位置X， 当前位置Y， 车辆编号（空载时为0）) 。。。(机器人编号n-1，当前位置X， 当前位置Y， 车辆编号（空载时为0）)
1 (机器人编号0，当前位置X， 当前位置Y， 车辆编号（空载时为0）) 。。。(机器人编号n-1，当前位置X， 当前位置Y， 车辆编号（空载时为0）)
.
。
。
M (机器人编号0，当前位置X， 当前位置Y， 车辆编号（空载时为0）) 。。。(机器人编号n-1，当前位置X， 当前位置Y， 车辆编号（空载时为0）)
如果机器人个数为0，那么M为0，输出结束。如下：
YES
0 3200 0 0
输出示例：
YES
2 175 714 79
0 (0,5,0,1) (1,5,0,0)
1 (0,4,0,1) (1,5,0,0)
2 (0,4,1,1) (1,5,0,0)
3 (0,4,2,1) (1,5,0,2)
4 (0,5,2,1) (1,4,0,2)
5 (0,4,2,0) (1,3,0,2)
6 (0,4,1,0) (1,2,0,2)
7 (0,4,0,0) (1,1,0,2)
8 (0,5,0,0) (1,0,0,2)
9 (0,5,0,0) (1,0,1,2)
10 (0,5,0,3) (1,0,2,2)
11 (0,4,0,3) (1,1,2,2)
12 (0,3,0,3) (1,1,2,0)
13 (0,2,0,3) (1,1,2,0)
14 (0,1,0,3) (1,1,2,0)
15 (0,0,0,3) (1,1,2,0)
16 (0,0,1,3) (1,1,2,0)
17 (0,0,2,3) (1,1,2,0)
18 (0,0,3,3) (1,0,2,0)
19 (0,1,3,3) (1,0,1,0)
20 (0,0,3,0) (1,0,0,0)
21 (0,0,2,0) (1,1,0,0)
22 (0,1,2,0) (1,2,0,0)
23 (0,1,2,0) (1,3,0,0)
24 (0,1,2,0) (1,4,0,0)
25 (0,1,2,0) (1,5,0,4)
26 (0,1,2,0) (1,4,0,4)
27 (0,1,2,0) (1,4,1,4)
28 (0,1,2,0) (1,4,2,4)
29 (0,1,2,0) (1,4,3,4)
30 (0,1,2,0) (1,5,3,4)
31 (0,1,2,0) (1,4,3,0)
32 (0,1,2,0) (1,4,2,0)
33 (0,1,2,0) (1,5,2,0)
34 (0,1,2,0) (1,5,2,0)
35 (0,1,2,0) (1,5,2,0)
36 (0,1,2,0) (1,5,2,0)
37 (0,1,2,0) (1,5,2,0)
38 (0,1,2,0) (1,5,2,0)
39 (0,1,2,0) (1,5,2,0)
40 (0,1,2,0) (1,5,2,0)
41 (0,1,2,0) (1,5,2,0)
42 (0,1,2,0) (1,5,2,1)
43 (0,1,2,0) (1,4,2,1)
44 (0,1,2,0) (1,4,3,1)
45 (0,1,2,2) (1,4,4,1)
46 (0,0,2,2) (1,4,5,1)
47 (0,0,1,2) (1,3,5,1)
48 (0,0,0,2) (1,3,4,0)
49 (0,1,0,2) (1,3,3,0)
50 (0,2,0,2) (1,3,2,0)
51 (0,2,1,2) (1,3,1,0)
52 (0,3,1,2) (1,3,0,0)
53 (0,3,2,2) (1,2,0,0)
54 (0,3,3,2) (1,1,0,0)
55 (0,3,4,2) (1,0,0,0)
56 (0,3,5,2) (1,0,1,0)
57 (0,4,5,0) (1,0,2,0)
58 (0,4,4,0) (1,0,3,0)
59 (0,4,3,0) (1,1,3,0)
60 (0,5,3,4) (1,1,3,0)
61 (0,4,3,4) (1,1,3,0)
62 (0,4,4,4) (1,1,3,0)
63 (0,4,5,4) (1,1,3,0)
64 (0,3,5,4) (1,1,3,0)
65 (0,3,5,0) (1,1,3,0)
66 (0,3,5,0) (1,1,3,0)
67 (0,3,5,0) (1,1,3,3)
68 (0,3,5,0) (1,0,3,3)
69 (0,3,5,0) (1,0,2,3)
70 (0,3,5,0) (1,0,1,3)
71 (0,3,5,0) (1,0,0,3)
72 (0,3,5,0) (1,1,0,3)
73 (0,3,5,0) (1,2,0,3)
74 (0,3,5,0) (1,2,1,3)
75 (0,3,5,0) (1,3,1,3)
76 (0,3,5,0) (1,3,2,3)
77 (0,3,5,0) (1,3,3,3)
78 (0,3,5,0) (1,3,4,3)
79 (0,3,5,0) (1,3,5,3)
补充说明
1.泊车机器人初始位置都在入口I处。
2.泊车机器人在没有收到申请出库之前不能在车位上搬运汽车。即车一旦到达车位后，只有收到离开命令后才能搬运。
3.同时申请入库（出库）的车辆顺序由机器人决定，不同时间的先申请先处理。申请入库和出库之间没有时间关系（例：A先申请入库，B后申请出库，机器人可以先执行B，再执行A）。补充：评判程序对于出库的先后顺序不做判断。
4.车位有空的情况下，泊车机器人空闲时且入口有车辆等待入库，不能拒载。补充：评判程序对于拒载不做判断，根据自己需要可以选择合适的车辆。
5.编程所使用的语言为C,C++,JAVA；不能使用第三方开源库，也不能使用操作系统的特效函数。
6.如果总共12个case，所有的case机器人数目为1，或者0的答案视为无效。只要有一个大于1就有效。case的机器人价格可能会很低
7.特别说明，注意代码规范，代码注释。进入总决赛者需要必要的文档，PPT，流程图等说明，
8.由于行驶过程中可以等待，因此用例无法保证每辆车都能入库，即有可能出现还没到车位就收到出库命令，这个时候，可以直接搬运到出口。但是到车位后，必须收到出库命令才能搬运，这点与补充说明2保持一样
9.运行环境
硬件环境：至强E5 2650 V4 8核心；
最大内存：2G；
运行时间：100S以内
GCC版本：4.8.2
JAVA版本：JDK 1.7.0_80
示例展示
K=1, p=80,a=400,b=5
一种策略如下：
对于该策略，用了一辆泊车机器人，时间T = 120+90+110 =400， 能耗W =200+120+96=416。这个策略得到的Z不一定是最小的，因此现在需要参赛者提供的程序能够针对不同的比赛用例，给出Z最小即可，即不存在标准答案，参赛者给出自认为可行的方案即可。
海康威视复赛题