华为OD(C卷,200分)- 智能驾驶

    #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;
    
    // m * n 的地图
    int m, n;
    // 地图矩阵
    int matrix[MAX_SIZE][MAX_SIZE];
    
    // 上下左右四个方向对应的偏移量
    int offsets[4][2] = {{-1, 0},
                     {1,  0},
                     {0,  -1},
                     {0,  1}};
    
    int bfs() {
    // 如果左上角和右下角不可达，则直接返回-1
    if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
        return -1;
    }
    
    // 广搜队列
    int head = 0;
    int tail = 0;
    Node queue[MAX_SIZE * MAX_SIZE];
    
    // 起始位置
    Node src;
    src.x = 0;
    src.y = 0;
    
    if (matrix[0][0] == -1) {
        // 如果起始位置就是加油站，则到达(0,0)位置所需初始油量为0，且剩余可用油量为100，且需要标记已加油
        src.init = 0;
        src.remain = 100;
        src.flag = 1;
    } else {
        // 如果起始位置不是加油站，则到达(0,0)位置所需的初始油量至少为matrix[0][0], 剩余可用油量为0，未加油状态
        src.init = matrix[0][0];
        src.remain = 0;
        src.flag = 0;
    }
    
    // 将起始位置加入队列
    queue[tail++] = src;
    
    // dist_init[x][y] 用于记录起点 (0, 0) 到达 (x, y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的初始油量
    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;
        }
    }
    
    // dist_remain 用于记录起点 (0,0) 到达 (x,y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的最大剩余可用油量
    // 即如果存在多条最优路径，我们应该选这些路径中到达此位置剩余油量最多的
    int dist_remain[MAX_SIZE][MAX_SIZE] = {0};
    
    // 起点（0,0）到达自身位置（0,0）所需的最少初始油量和最多剩余油量
    dist_init[0][0] = src.init;
    dist_remain[0][0] = src.remain;
    
    // 广搜
    while (head != tail) {
        Node cur = queue[head++];
    
        // 从当前位置cur开始向上下左右四个方向探路
        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 {
                // 如果新位置不是加油站，则需要消耗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队列
                queue[tail++] = (Node) {newX, newY, init, remain, flag};
            }
        }
    }
    
    // dist_init[m - 1][n - 1] 记录的是到达右下角终点位置所需的最少初始油量
    if (dist_init[m - 1][n - 1] == INT_MAX) {
        return -1;
    } else {
        return dist_init[m - 1][n - 1];
    }
    }
    
    int main() {
    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;
    }