题目概述
在车库中安排若干泊车机器人，根据给定的车位地图，合理优化机器人的数量及其运动路径，尽量减少客户在停车和取车中的等待时间，并使总成本最小。（试题用例包于5月初开放下载）
参数设定
为了简化问题，我们对泊车机器人的实际运行情况做出如下规定和说明，与“题目背景”中所述的泊车机器人真实运行情况有所不同，请注意。
地图说明：
给定一个停车地图，以下图为例：地图中红色部分表示车位（P），黑色部分表示障碍物（B），黄色部分表示入口（I），绿色部分表示出口（E），白色表示行车道路（X），每个车位都与行车道路（X）相邻，每个车位（P）只能停一辆车。
1.泊车机器人必须能到达每个车位；
2.每个车位有且只有一个入口, 即每个红色区域旁边有且只有一个白色区域；
3.出口和入口各只有一个，且不重合，分布在地图边缘，泊车机器人从入口和出口都能到达每个车位。
泊车机器人说明：
1.泊车机器人（R）运行速度为每秒一个格，且只能向前、后、左、右移动，不能沿对角线移动。
2.泊车机器人不论在载车还是空车状态，都不能穿过图例中黑色区域（B）；且只能由白色区域（X）进入到红色区域（P），或相反；不能在红色区域（P）之间移动。比如，上图图例中左上角， 允许3->1和1->3，但不允许1->2。
3.泊车机器人在搬运车辆的过程中不能停车等待。
4.泊车机器人在空闲的时候，可以行驶到任何位置（除了B区域）。
5.允许多个泊车机器人相遇，泊车机器人之间不会发生碰撞；允许多个泊车机器人同一时间出现在同一格子中。
6.假设泊车机器人空载时耗能极少可忽略不计，载车时能耗（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.从标准输入 输入的数据以空格分隔，每行以换行符（‘ ’）结尾。
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 80 400 5 //能耗系数k:1， 罚时系数p:80， 泊车机器人系数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 50 20 10 // 车辆编号为1，申请进入时间点为0，申请离开时间点50，最大等地时间20，质量为10，即车辆如果在0+20这个时间点还没有被接走，就表示该车放弃泊车。
2 3 45 15 15
3 10 64 10 11
4 25 60 20 12
输出
1.标准输出，输出的数据以空格分隔，每行以换行符（‘ ’）结尾。
2.输出格式：
首先判断给的用例地图是否有效（判断依据见地图说明），
如果地图无效则：NO
文件结束
如果地图有效：YES
泊车机器人个数n 所有车的等待时间T（b*T1+T2） 所有泊车机器人的总能耗W
1 是否放弃停车，是输出yes该行结束
2 是否放弃停车，否输出no 入库泊车机器人编号（0开始） 入库时间点（机器人从入库处搬运的时间点） 入库路径 出库泊车机器人编号 出库时间点（泊车机器人从车位搬运的时间点） 出库路径
.
.
N-1 no入库泊车机器人编号（0开始） 入库时间点（机器人从入库处搬运的时间点） 入库路径 出库泊车机器人编号 出库时间点（泊车机器人从车位搬运的时间点） 出库路径
N yes
输出示例：
YES
1 400 416 // 需要泊车机器人1辆，总的等待时间为400 机器人总能耗416
1 no 0 0 (4,0) (3,0) (2,0) (1,0) (0,0) (0,1) (0,2) (0,3) (1,3) 0 62 (1,3) (0,3) (0,2) (0,1) (0,0) (1,0) (2,0) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5)
2 no 0 16 (4,0) (4,1) (4,2) (5,2) 0 45 (5,2) (4,2) (3,2) (3,3) (3,4) (3,5)
3 yes
4 no 0 25 (4,0) (4,1) (4,2) (4,3) (5,3) 0 78 (5,3) (4,3) (3,3) (3,4) (3,5)
补充说明
1.泊车机器人初始位置都在入口I处。
2.泊车机器人在没有收到申请出库之前不能在车位上搬运汽车。即车一旦到达车位后，只有收到离开命令后才能搬运。
3.同时申请入库（出库）的车辆顺序由机器人决定，不同时间的先申请先处理。申请入库和出库之间没有时间关系（例：A先申请入库，B后申请出库，机器人可以先执行B，再执行A）。
4.车位有空的情况下，泊车机器人空闲时且入口有车辆等待入库，不能拒载。
5.泊车机器人入库或者出库的过车中，行驶里程不能大于整个地图的空闲区域数。
6.泊车机器人接到车辆后有足够长的时间把车放在车位，即输入的case中保证申请离开时间(T-out)＞实际进入时间（T-in＇）+地图全部白色区域的格子数。因此入库的车必定要在停车位上停过。
7.编程所使用的语言为C,C++,JAVA；不能使用第三方开源库，也不能使用操作系统的特效函数。
8.运行环境
硬件环境：至强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最小即可，即不存在标准答案，参赛者给出自认为可行的方案即可。
评判标准
对于地图有误的用例：
1.地图判断错误，得0分。
2.地图判断正确，按程序运行时间排名，越短排名越靠前。
对于地图无误的用例：
1.计算出来的Z跟实际给出的车辆路径计算出来的T,W等数据不符合得0分。
2.验证系统会根据给出的路径，模拟泊车机器人运行过程，查看是否存在同一时间点同一泊车机器人搬运多辆车，或者是否存在泊车机器人跳跃移动情况，如果存在得0分。
3.车辆路径存在冲突，或者根本不可能完成（例如泊车机器人同时搬运多辆车的情况），得0分。
4.路径以及给出的Z都符合要求的情况，Z越小，排名越靠前。
5.对于给出的Z相同，程序运行时间越短的，排名越靠前。
对于单个用例，排名第一的得100分，其他的依次降低。
总的分数为：单个用例分数总和/用例个数。
不同队伍提交的答案严禁抄袭雷同，一旦发现不诚信行为，将取消参赛资格并进入黑名单。
赛事讨论交流群
欢迎加入QQ群交流讨论大赛技术及赛制问题！
软件精英挑战赛全国1群：537539505
关注海康威视招聘官方公众号获取大赛及校园招聘实时信息！
海康威视招聘官方公众号：HikvisionHR
特别申明
1．参赛作品必须是原创作品，未侵犯第三方知识产权。且该作品未在报刊、杂志、网站（含开源社区）及其他媒体公开发表，未申请专利或进行版权登记的作品，未参加过其他比赛，未以任何形式进入商业渠道。
2．参赛者或参赛团体同意，获奖作品相关知识产权归海康威视所有。获奖者不以同一作品形式参加其他的设计比赛或转让给他方；否则，海康威视将取消其参赛、入围与获奖资格，收回奖品及并保留追究法律责任的权利。
3．因参赛作品而引发的第三方侵权纠纷，由参赛者或参赛团体承担全部法律责任。