华为OD机试算法：智能驾驶

题目描述

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

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

说明：

输入描述

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

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

输出描述

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

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

用例

题目解析

注意：

题目解析

1.

创建一个优先队列（以油量为键），并将起点(0, 0, 0)加入队列。（这里假设起始油量为0，因为我们要找的是最少初始油量）

2.

创建一个集合或数组来记录已经访问过的状态，以避免重复搜索。

3.

当队列不为空时，执行以下操作： a. 弹出队列中油量最少的节点(x, y, oil)。 b. 如果(x, y)是终点，那么我们找到了一条路径，返回oil即为所求。 c. 否则，遍历该节点的所有合法邻居（即没有障碍物并且不超出边界的节点）。 d. 对于每个邻居(nx, ny)，计算经过该邻居后的油量newOil = oil - cost[nx][ny]，如果newOil < 0则忽略该邻居（因为不能到达）。 e. 如果(nx, ny, newOil)未被访问过，将其加入优先队列，并标记为已访问。

4.

如果队列变空也没有找到终点，说明无法到达，返回-1。

注意：

在步骤3中，每次移动到加油站时，需要将油量设为最大值（例如100），这代表加满油。

在实际应用中，可能需要优化算法来减少搜索空间，例如通过剪枝技巧去除明显不可达的状态。

JS算法源码
const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin });

(async function () {
  const [m, n] = (await new Promise((resolve) => rl.question("", resolve))).split(",").map(Number);

  const matrix = [];
  for (let i = 0; i < m; i++) {
    matrix.push((await new Promise((resolve) => rl.question("", resolve))).split(",").map(Number));
  }

  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  class Node {
    constructor(x, y) {
      this.x = x;
      this.y = y;
      this.init = 0;
      this.remain = 0;
      this.flag = false;
    }
  }

  function bfs() {
    if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
      return -1;
    }

    const queue = [];
    const src = new Node(0, 0);

    if (matrix[0][0] == -1) {
      src.init = 0;
      src.remain = 100;
      src.flag = true;
    } else {
      src.init = matrix[0][0];
      src.remain = 0;
      src.flag = false;
    }

    queue.push(src);

    const dist_init = Array.from({ length: m }, () => Array(n).fill(Infinity));
    const dist_remain = Array.from({ length: m }, () => Array(n).fill(0));

    dist_init[0][0] = src.init;
    dist_remain[0][0] = src.remain;

    while (queue.length > 0) {
      const cur = queue.shift();

      for (let [offsetX, offsetY] of offsets) {
        const newX = cur.x + offsetX;
        const newY = cur.y + offsetY;

        if (
          newX < 0 ||
          newX >= m ||
          newY < 0 ||
          newY >= n ||
          matrix[newX][newY] == 0
        ) {
          continue;
        }

        let init = cur.init;
        let remain = cur.remain;
        let flag = cur.flag;

        if (matrix[newX][newY] == -1) {
          remain = 100;
          flag = true;
        } else {
          remain -= matrix[newX][newY];
        }

        if (remain < 0) {
          if (flag) {
            continue;
          } else {
            init -= remain;
            remain = 0;
          }
        }

        if (init > 100) {
          continue;
        }

        if (init > dist_init[newX][newY]) {
          continue;
        }

        if (init < dist_init[newX][newY] || remain > dist_remain[newX][newY]) {
          dist_init[newX][newY] = init;
          dist_remain[newX][newY] = remain;

          const next = new Node(newX, newY);
          next.init = init;
          next.remain = remain;
          next.flag = flag;

          queue.push(next);
        }
      }
    }

    return dist_init[m - 1][n - 1] == Infinity ? -1 : dist_init[m - 1][n - 1];
  }

  console.log(bfs());
})();

Java算法源码
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int m;
    static int n;
    static int[][] matrix;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(bfs());
    }

    // 上下左右四个方向对应的偏移量
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 记录路径中位置的几个状态
    static class Node {
        int x; // 位置横坐标
        int y; // 位置纵坐标
        int init; // 到达此位置所需的最少初始油量
        int remain; // 到达此位置时剩余可用油量
        boolean flag; // 到达此位置前有没有加过油

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

    public static int bfs() {
        // 如果左上角和右下角不可达，则直接返回-1
        if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
            return -1;
        }

        // 广搜队列
        ArrayList<Node> queue = new ArrayList<>();

        // 起始位置
        Node src = new Node(0, 0);

        if (matrix[0][0] == -1) {
            // 如果起始位置就是加油站，则到达(0,0)位置所需初始油量为0，且剩余可用油量为100，且需要标记已加油
            src.init = 0;
            src.remain = 100;
            src.flag = true;
        } else {
            // 如果起始位置不是加油站，则到达(0,0)位置所需的初始油量至少为matrix[0][0], 剩余可用油量为0，未加油状态
            src.init = matrix[0][0];
            src.remain = 0;
            src.flag = false;
        }

        queue.add(src);

        // dist_init[x][y] 用于记录起点 (0, 0) 到达 (x, y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的初始油量
        int[][] dist_init = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 由于需要记录每个位置的最少需要的初始油量，因此每个位置所需的初始油量初始化为一个较大值
                dist_init[i][j] = Integer.MAX_VALUE;
            }
        }

        // dist_remain 用于记录起点 (0,0) 到达 (x,y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的最大剩余可用油量
        // 即如果存在多条最优路径，我们应该选这些路径中到达此位置剩余油量最多的
        int[][] dist_remain = new int[m][n];

        // 起点（0,0）自身到达自身位置（0,0）所需的最少初始油量和最多剩余油量
        dist_init[0][0] = src.init;
        dist_remain[0][0] = src.remain;

        // 广搜
        while (queue.size() > 0) {
            Node cur = queue.remove(0);

            // 从当前位置cur开始向上下左右四个方向探路
            for (int[] offset : offsets) {
                // 新位置
                int newX = cur.x + offset[0];
                int newY = cur.y + offset[1];

                // 新位置越界 或者 新位置是障碍，则新位置不可达，继续探索其他方向
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || matrix[newX][newY] == 0) continue;

                // 如果新位置可达，则计算到达新位置的三个状态数据
                int init = cur.init; // 到达新位置所需的最少初始油量
                int remain = cur.remain; // 到达新位置时还剩余的最多可用油量
                boolean flag = cur.flag; // 是否加油了

                if (matrix[newX][newY] == -1) {
                    // 如果新位置是加油站，则加满油
                    remain = 100;
                    // 标记加过油了
                    flag = true;
                } else {
                    // 如果新位置不是加油站，则需要消耗matrix[newX][newY]个油
                    remain -= matrix[newX][newY];
                }

                // 如果到达新位置后，剩余油量为负数
                if (remain < 0) {
                    if (flag) {
                        // 如果之前已经加过油了，则说明到达此路径前是满油状态，因此我们无法从初始油量里面"借"油
                        continue;
                    } else {
                        // 如果之前没有加过油，则超出的油量（-remain），可以从初始油量里面"借"，即需要初始油量 init + (-remain) 才能到达新位置
                        init -= remain;
                        // 由于初始油量 init + (-remain) 刚好只能支持汽车到达新位置，因此汽车到达新位置后剩余可用油量为0
                        remain = 0;
                    }
                }

                // 如果到达新位置所需的初始油量超过了满油100，则无法到达新位置
                if (init > 100) {
                    continue;
                }

                // 如果可达新位置，则继续检查当前路径策略到达新位置(newX, newY)所需的初始油量init是否比其他路径策略更少
                if (init > dist_init[newX][newY]) {
                    // 如果不是，则无需探索新位置(newX, newY)
                    continue;
                }

                // 当前路径策略到达新位置(newX,newY)所需初始油量init更少，或者，init和前面路径策略相同，但是当前路径策略剩余可用油量remain更多
                if (init < dist_init[newX][newY] || remain > dist_remain[newX][newY]) {
                    // 则当前路径策略更优，记录更优路径的状态
                    dist_init[newX][newY] = init;
                    dist_remain[newX][newY] = remain;

                    // 将当前新位置加入BFS队列
                    Node next = new Node(newX, newY);
                    next.init = init;
                    next.remain = remain;
                    next.flag = flag;

                    queue.add(next);
                }
            }
        }

        // dist_init[m - 1][n - 1] 记录的是到达右下角终点位置所需的最少初始油量
        return dist_init[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dist_init[m - 1][n - 1];
    }
}

Python算法源码
import sys
from collections import deque

# 输入获取
m, n = map(int, input().split(","))
matrix = [list(map(int, input().split(","))) for _ in range(m)]

# 上下左右四个方向对应的偏移量
offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

# 记录路径中位置的几个状态
class Node:
    def __init__(self, x, y):
        self.x = x  # 位置横坐标
        self.y = y  # 位置纵坐标
        self.init = 0  # 到达此位置所需的最少初始油量
        self.remain = 0  # 到达此位置时剩余可用油量
        self.flag = False  # 到达此位置前有没有加过油

# 算法入口
def bfs():
    if matrix[0][0] == 0 or matrix[m - 1][n - 1] == 0:
        return -1

    queue = deque()
    src = Node(0, 0)

    if matrix[0][0] == -1:
        src.init = 0
        src.remain = 100
        src.flag = True
    else:
        src.init = matrix[0][0]
        src.remain = 0
        src.flag = False

    queue.append(src)

    dist_init = [[sys.maxsize] * n for _ in range(m)]
    dist_remain = [[0] * n for _ in range(m)]

    dist_init[0][0] = src.init
    dist_remain[0][0] = src.remain

    while queue:
        cur = queue.popleft()

        for offsetX, offsetY in offsets:
            newX = cur.x + offsetX
            newY = cur.y + offsetY

            if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 0:
                continue

            init = cur.init
            remain = cur.remain
            flag = cur.flag

            if matrix[newX][newY] == -1:
                remain = 100
                flag = True
            else:
                remain -= matrix[newX][newY]

            if remain < 0:
                if flag:
                    continue
                else:
                    init -= remain
                    remain = 0

            if init > 100:
                continue

            if init > dist_init[newX][newY] or (init == dist_init[newX][newY] and remain > dist_remain[newX][newY]):
                dist_init[newX][newY] = init
                dist_remain[newX][newY] = remain

                nxt = Node(newX, newY)
                nxt.init = init
                nxt.remain = remain
                nxt.flag = flag

                queue.append(nxt)

    if dist_init[m - 1][n - 1] == sys.maxsize:
        return -1
    else:
        return dist_init[m - 1][n - 1]

print(bfs())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_SIZE 200

typedef struct {
    int x; // 位置横坐标
    int y; // 位置纵坐标
    int init; // 到达此位置所需的最少初始油量
    int remain; // 到达此位置时剩余可用油量
    int flag; // 到达此位置前有没有加过油
} Node;

Node *new_Node(int x, int y) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->x = x;
    node->y = y;
    node->init = 0;
    node->remain = 0;
    node->flag = 0;
    return node;
}

typedef struct ListNode {
    Node *ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, Node *ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

Node *removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    return removed->ele;
}

int bfs();

int main() {
    int m, n;
    scanf("%d,%d", &m, &n);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
            getchar();
        }
    }

    printf("%d\n", bfs());

    return 0;
}

int bfs() {
    if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
        return -1;
    }

    LinkedList *queue = new_LinkedList();

    Node *src = new_Node(0, 0);

    if (matrix[0][0] == -1) {
        src->init = 0;
        src->remain = 100;
        src->flag = 1;
    } else {
        src->init = matrix[0][0];
        src->remain = 0;
        src->flag = 0;
    }

    addLast_LinkedList(queue, src);

    int dist_init[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dist_init[i][j] = INT_MAX;
        }
    }

    int dist_remain[MAX_SIZE][MAX_SIZE] = {0};

    dist_init[0][0] = src->init;
    dist_remain[0][0] = src->remain;

    while (queue->size > 0) {
        Node *cur = removeFirst_LinkedList(queue);

        for (int i = 0; i < 4; i++) {
            int newX = cur->x + offsets[i][0];
            int newY = cur->y + offsets[i][1];

            if (newX < 0 || newX >= m || newY < 0 || newY >= n || matrix[newX][newY] == 0) {
                continue;
            }

            int init = cur->init;
            int remain = cur->remain;
            int flag = cur->flag;

            if (matrix[newX][newY] == -1) {
                remain = 100;
                flag = 1;
            } else {
                remain -= matrix[newX][newY];
            }

            if (remain < 0) {
                if (flag) {
                    continue;
                } else {
                    init -= remain;
                    remain = 0;
                }
            }

            if (init > 100) {
                continue;
            }

            if (init > dist_init[newX][newY]) {
                continue;
            }

            if (init < dist_init[newX][newY] || remain > dist_remain[newX][newY]) {
                dist_init[newX][newY] = init;
                dist_remain[newX][newY] = remain;

                Node *next = new_Node(newX, newY);
                next->init = init;
                next->remain = remain;
                next->flag = flag;

                addLast_LinkedList(queue, next);
            }
        }
    }

    if (dist_init[m - 1][n - 1] == INT_MAX) {
        return -1;
    } else {
        return dist_init[m - 1][n - 1];
    }
}