[华为OD]BFS C卷 200 智能驾驶

题目：

有一辆汽车需要从m*n的地图的左上角(起点)开往地图的右下角(终点)，去往每一个地区都需 

要消耗一定的油量，加油站可进行加油

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

(1)智能汽车可以上下左右四个方向移动1

⑵地图上的数字取值是0或-1或者正整数：

-1：表示加油站，可以加满油，汽车的油箱容量最大为100；

0：表示这个地区是障碍物，汽车不能通过

正整数:表示汽车走过这个地区的耗油量

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

输入描述

第一行为两个数字，M, V,表示地图的大小为M,N(0< M,N < 200)

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

输出描述

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

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

示例1 

输入

2,2 

10,20 

30,40

输出

70

示例2 

输入

4,4 

10,30,30,20 

30,30,-1,10 

0,20,20,40

10,-1,30,40 

输出

70

示例3

输入

4,5

10,0,30,-1,10 

30,0,20,0,20 

10,0,10,0,30 

10,-1,30,0,10 

输出

60

示例4

输入

4,4

10,30,30,20 

30,30,20,10 

10,20,10,40 

10,20,30,40 

输出

-1

题解：这个题目要计算最少初始油料，那么如果经过加油站的话，明显就要直接加满油。

比较明显的BFS题目。但是需要判断到加油站的情况。由于油箱容量100，那么我们出发时候就将当前油量设置为100。

依旧还是需要定义一个内部类，参数有x,y坐标。这个里面就加了，初始油量originalOil，当前坐标走完需要油量needOil,也就是矩阵中当前的值。以及汽车在这个坐标的剩余油量restOil，还有一个bool值，是否有在加油站加过油。

1）如果到加油站时候，车辆没有加过油，那么从出发到这个加油站的初始油量（刚出发时候初始油量）就可以变为100减去当前剩余油量了。

2）当BFS向下一坐标搜索的时候，如果restOil剩余油量不足以满足去下一个坐标需要的油量needOil，那么就继续往下搜索

3）在到终点的时候，如果没有加过油，那么如果剩余油量>0,那么这个路径走下来的初始油量应该可以变成100减去当前剩余油量

4）当走到任意坐标时候，油量足够，而且汽车加过油，那么初始油量应该不变，因为加过油，剩余油量在加油站那个坐标直接变为100了

5）走过一个坐标，那么这个坐标访问标记visit[x][y]=1;

这个里面可以看到有一个难点就是可能有两条路线能经过同一个加油站，两条路径油量不同，如何确保最终是最少油量经过这个加油站。这边采用的是一个map<String,Integer> oilStations来解决表示的是这个加油站坐标和来这个加油站最少得油量。因为在初始化扫描的时候当矩matrixs[i][j]==-1,就是加油站，那么此时就初始化这个加油站油量为Integer.MaxValue.

6）那么在经过加油站的坐标时候，加油站坐标的visit[x][y]，还是为0，不能变为1，防止其他路径更少油量，由于visit[x][y]==1，而不能到加油站，结果就不对。此时，先根据oilStations，拿到抵达这个加油站当前的最少油量prsentLeastOil，如果这个路径到这个加油站的最少油量小于

prsentLeastOil，那么说明现在这个路径就更优，那么就把这个路径继续扫描下去，也就是将这个路径的点加入到队列中去。如果大于等于，这条路径就不用继续扫描了，明显不是最优解，不能为等于是因为防止两个加油站相邻，那么等于的话，明显路径会在这两个加油站一直循环扫。

7）用一个列表表示每个到终点的路径最少油量，最后排序取第一个值就是最少初始油量了

这个题感觉难度就在处理加油站的逻辑上面。

代码：

import java.util.*;

public class CarPath {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] matrix = sc.nextLine().split(",");
        int m = Integer.valueOf(matrix[0]);
        int n = Integer.valueOf(matrix[1]);
        int matrixs[][] = new int[m][n];
        int visit[][] = new int[m][n];
        Map<String, Integer> oilStations = new HashMap<>();
        for (int i = 0; i < m; i++) {
            String[] data = sc.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                matrixs[i][j] = Integer.valueOf(data[j]);
                visit[i][j] = 0;
                if (matrixs[i][j] == -1) {
                    oilStations.put(String.valueOf(i) + String.valueOf(j), Integer.MAX_VALUE);
                }
            }
        }

        int startX = 0;
        int startY = 0;
        int endX = m - 1;
        int endY = n - 1;
        Path startPath = new Path(startX, startY, matrixs[0][0], 100 - matrixs[0][0]);
        startPath.originalOil = 100;
        visit[0][0] = 1;
        Queue<Path> queue = new LinkedList<>();
        queue.offer(startPath);

        List<Integer> needOil = new ArrayList<>();
        boolean hasRoote = false;

        int dirctions[][] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        // BFS
        while (!queue.isEmpty()) {
            Path frontPath = ((LinkedList<Path>) queue).getFirst();
            if (frontPath.x == endX && frontPath.y == endY) {
                hasRoote = true;
                ((LinkedList<Path>) queue).pollFirst();
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int newX = frontPath.x + dirctions[i][0];
                int newY = frontPath.y + dirctions[i][1];

                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    System.out.println("newX " + newX + " newY " + newY);
                    if (newX == 3 && newY == 3) {
                        System.out.println("error0");
                    }
                    if (newX == endX && newY == endY) { // 下一个是终点
                        Path endPath = new Path(newX, endY, matrixs[newX][newX], frontPath.getRestOil() - matrixs[newX][newX]);
                        if (endPath.restOil < 0) { // 油不足以走到终点
                            continue;
                        } else {
                            if (frontPath.hasAddOil) { //加过油
                                endPath.originalOil = frontPath.originalOil;
                            } else {//全程没有加过油 并且有多的油
                                endPath.originalOil = frontPath.originalOil - endPath.restOil;
                            }
                            needOil.add(endPath.originalOil);
                            hasRoote = true;
                            queue.offer(endPath);
                            continue;
                        }
                    }

                    if (matrixs[newX][newY] != 0 && matrixs[newX][newY] != -1 && visit[newX][newY] == 0) { //下一个是一般道路
                        Path nextPath = new Path(newX, newY, matrixs[newX][newY],
                                frontPath.getRestOil() - matrixs[newX][newY]);
                        if (nextPath.restOil < 0) { // 油不足以走到终点
                            continue;
                        } else {
                            nextPath.hasAddOil = frontPath.hasAddOil;
                            if (frontPath.hasAddOil) {//加过油
                                nextPath.originalOil = frontPath.originalOil;
                            } else { //没加过油 需要的油就要加上当前道路需要的油
                                nextPath.originalOil = frontPath.originalOil;
                            }
                        }
                        if (nextPath.x == 3 && nextPath.y == 3) {
                            System.out.println("error");
                        }
                        queue.offer(nextPath);
                        visit[newX][newY] = 1;
                        continue;
                    }

                    if (matrixs[newX][newY] == 0) {
                        visit[newX][newY] = 1;
                        continue;
                    }
                    if (matrixs[newX][newY] == -1 && visit[newX][newY] == 0) { // 到加油站了，这个题明显到加油站都得加满油
                        Integer prsentLeastOil = oilStations.get(String.valueOf(newX) + String.valueOf(newY));
                        if (frontPath.restOil >= prsentLeastOil) {
                            continue;
                        }
                        oilStations.put(String.valueOf(newX) + String.valueOf(newY), frontPath.restOil);
                        Path nextPath = new Path(newX, newY, matrixs[newX][newY],
                                100);// 加油站直接加满油
                        nextPath.hasAddOil = true;
                        if (!frontPath.hasAddOil) {// 前面没有加过油
                            nextPath.originalOil = frontPath.originalOil - frontPath.restOil;// 需要的油应该是前车需要的油料减去前车剩余油料，因为初始化是100
                        } else { // 前面已经加过油
                            nextPath.originalOil = frontPath.originalOil;
                        }
                        visit[newX][newY] = 0;  //加油站不设置访问标记 通过判断到加油站剩余油料是最少得来判断是否将当前数据加入队列，继续扫描
                        if (nextPath.x == 3 && nextPath.y == 3) {
                            System.out.println("error1");
                        }
                        queue.offer(nextPath);
                        continue;
                    }
                }
            }

            ((LinkedList<Path>) queue).pollFirst(); //首元素推出队列
        }

        if (hasRoote) {
            Collections.sort(needOil);
            System.out.println(needOil.get(0));
        } else {
            System.out.println(-1);
        }


    }

    private static class Path {
        int x;
        int y;
        int needOil;
        int restOil;
        int originalOil;
        boolean hasAddOil;//是否加过油

        public Path(int x, int y, int needOil) {
            this.x = x;
            this.y = y;
            this.needOil = needOil;
        }

        public Path(int x, int y, int needOil, int restOil) {
            this.x = x;
            this.y = y;
            this.needOil = needOil;
            this.restOil = restOil;
        }


        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getNeedOil() {
            return needOil;
        }

        public void setNeedOil(int needOil) {
            this.needOil = needOil;
        }

        public int getRestOil() {
            return restOil;
        }

        public void setRestOil(int restOil) {
            this.restOil = restOil;
        }

        public Path(int originalOil) {
            this.originalOil = originalOil;
        }

        public Path(boolean hasAddOil) {
            this.hasAddOil = hasAddOil;
        }
    }
}

验证：