华为OD统一考试 - 智能驾驶

题目描述

有一辆汽车需要从 m * n 的地图左上角（起点）开往地图的右下角（终点），去往每一个地区都需要消耗一定的油量，加油站可进行加油。

请你计算汽车确保从从起点到达终点时所需的最少初始油量。

说明：

1. 智能汽车可以上下左右四个方向移动
2. 地图上的数字取值是 0 或 -1 或 正整数：     

• -1 ：表示加油站，可以加满油，汽车的油箱容量最大为100
• 0 ：表示这个地区是障碍物，汽车不能通过
• 正整数：表示汽车走过这个地区的耗油

3.如汽车无论如何都无法到达终点，则返回 -1

输入描述

第一行为两个数字，M，N，表示地图的大小为 M * N

• 0 < M,N ≤ 200

后面一个 M * N 的矩阵，其中的值是 0 或 -1 或正整数，加油站的总数不超过 200 个

输出描述

如果汽车无论如何都无法到达终点，则返回 -1

如果汽车可以到达终点，则返回最少的初始油量

用例

题目解析

用例1路径

用例2路径

用例3路径

用例4：

由于汽车油箱容量最大100，因此即使初始时加满了油，也无法找到一条路径从起点到达终点

本题我有一个疑问，那就是否可以走回头路？我这里走回头路的目的是：尽可能地经过加油站，比如下面例子：

3,3

10,-1,40

30,0,50

50,-1,40

路线图如下，先走红色箭头路线，之后走绿色箭头 

按照上面路线，初始只需要10个油即能完成从左上角开往右下角。

上面这种行驶路线我理解是可行的，也是符合本题要求的，同时也是符合实际生活场景的（车子快没油了，肯定是优先找一个就近的加油站先加油，即使加油站不在规划的路线上）。

本题的极限地图可以达到200*200，使用深搜DFS策略探路的话肯定会超时。

因此推荐使用广搜BFS策略探路。

当我们加起点加入到BFS队列后，此时即形成了一条路径，即起点(0,0)到(0,0)的路径，该路径的终点是(0,0)，因此我们可以理解加入BFS队列中的位置点其实可以对应为某条路径的终点位置。

当我们从BFS队列弹出一个位置点A，其实就是选择某条路径，并从该路径的终点A，继续向其上下左右四个方向探路：

• 如果新位置B越界，则无法访问B
• 如果新位置B是障碍物，则无法访问B

除了上面两个判断外，我们还需要对A位置如下信息进行分析：

• 当前路径到达A点时，还剩余多少可用的油量，假设剩余可用油量为：A.remain
• 当前路径到达A点的过程中是否加过油？假设加油状态为：A.flag
• 当前路径到达A点所需的最少初始油量，假设最少初始油量为：A.init

如果新位置B本身是加油站的话，那么A->B的过程中：

• B.remain = 100    // 汽车到B位置后，会加满油
• B.origin = A.origin        // 只需要 A.origin 初始油量也可以到达B位置
• B.flag = true         // 在B位置加油了

如果新位置B不是加油站的话，那么A->B的过程中：

• B.flag = A.flag                                      // 加油状态沿用之前的
• B.remain = A.remain - matrix[B.x][B.y]    // 汽车从A到B需要消耗matrix[B.x][B.y] 的油量，因此到B点后，剩余可用油量为 A.remain - matrix[B.x][B.y] 

此时 B.remain 可能是负数，也可能不是负数：

• 如果 B.remain 是负数的话，则说明从 A 位置靠 A.remain 的剩余可用油量无法到B位置，此时有一个办法，那就是将这部分缺额油量计入到当前路径的初始油量中，即当前路径从起点出发时多带一点初始油量，且至少需要 A.origin + (-B.remain) 初始油量，才能使得当前路径从起点到达B点，因此此时我们更新当前路径所需最少初始油量为 B.origin = A.origin + (-B.remain)，注意此时B点为当前路径新的终点，因此当前路径的最少初始油量信息更新到B点上。同时注意更新 B.remain = 0。
• 如果 B.remain >= 0 的话，则说明从A位置可以靠 A.remain 的剩余可用油量到达B位置，所以B.init = A.init，即当前路径只需要A.origin的初始油量，即可从起点到达B点。

注意：上面讨论 B.remain 是负数的时，表示当前路径到达B点还缺少（-B.remain）的油量，我们上面粗暴的将缺少的油量计入到了当前路径从起点出发时带的初始油量中，即初始油量多带（-B.remain）的油量，即可保证当前路径刚刚好到达B点时消耗完所有的油。

但是，上面这个粗暴计入是存在问题的，请看下图：

(0, 0) -> (0, 0) 至少需要初始油量10，如果初始油量10，那么此时剩余可用0

(0, 0) -> (1, 0) 至少需要初始油量40，如果初始油量40，那么此时剩余可用0

(0, 0) -> (1, 0) -> (2, 0) 至少需要初始油量40，此时加满了油，剩余可用100

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) 至少需要初始油量40，剩余可用30

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) 由于上一步剩余可用只有30，而到达终点(2,2)需要40的油量，还缺10个油，那么这里缺的10个油，能粗暴的计入到初始油量里面吗？

假设我们粗暴的计入到初始油量中，即当前路径从起点出发时初始油量50个，那么

(0, 0) -> (0, 0)，剩余可用40

(0, 0) -> (1, 0)，剩余可用10

(0, 0) -> (1, 0) -> (2, 0)，加满了油，剩余可用100

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) ，剩余可用30

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) ，此时上一步剩余油量还是不够？？？？为啥？

问题出在，该路径到达(2,2)前加过一次油了，因此该路径是从某个位置以满油状态来的，因此即使你给初始油量加再多，中间过程必然会变一次满油状态，而满油状态也无法到达(2,2)，因此该路径无法到达(2,2)。

总结一下就是，如果A->B过程中，油量不够了，此时我们期望是将缺额油量计入到初始油量中，但是到达B之前的过程中不能加过油，否则此时缺额的油无法通过初始油量补充得到。

还有一个问题，如果上面A->B缺少的油，可以计入到当前路径的初始油量中，那么如果是下面例子，还可以借吗？

即我们每走一步都将缺少油计入到初始油量中，但是汽车油箱只有100个单位，如果缺少的油超过了100个单位，那么对应路径也不大可达终点。

最后一个问题：本题允许回路，那么如何避免因为回路产生的死循环？

其实处理办法很简单，我们可以定义一个矩阵dist_origin，其中元素dist_origin[x][y] 用于记录起点到(x,y)的所有路径中的最优路径（即需要最少初始油量的路径）的初始油量。

每当我们BFS探索过（弹出）一个点（x,y）后，我们就得到了一条路径到达（x,y）点的最少初始油量origin，我们比较 origin 和 dist_origin[x][y]，

• 如果 origin < dist_origin[x][y]，则说明当前路径到达(x,y)更优，花费更少的初始油量 origin，此时我们更新 dist_origin[x][y] = origin
• 如果 origin > dist_origin[x][y]，则说明当前路径到达(x,y)不是最优的，因此当前路径也没必要继续往后探索了，可以终止当前路径的探索。

而回路是指(x1,y1) -> (x2, y2) -> (x1, y1)，如果 (x2, y2)不是加油站，那么此时(x2, y2) -> (x1, y1)的探路对应的origin，对于（x1, y1）