返回目录

题目描述

有一辆汽车需要从 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

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

示例：

题目解析

C算法源码

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

#define MAX_X 200 // x坐标的最大值
#define MAX_Y 200 // y坐标的最大值

// 位置结构体
typedef struct {
    int x; // x坐标
    int y; // y坐标
    int initialFuel; // 到达该位置所需的最小初始燃料
    int remainingFuel; // 到达该位置时剩余的燃料
    int fuelAdded; // 到达该位置前是否添加了燃料的标志
} Position;

// 创建新位置
Position *new_Position(int x, int y) {
    Position *position = (Position *)malloc(sizeof(Position));
    position->x = x;
    position->y = y;
    position->initialFuel = 0;
    position->remainingFuel = 0;
    position->fuelAdded = 0;
    return position;
}

// 链表节点结构体
typedef struct ListNode {
    Position *element;
    struct ListNode *next;
} ListNode;

// 链表结构体
typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

// 创建新链表
LinkedList *new_LinkedList() {
    LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// 将元素添加到链表末尾
void addLast_LinkedList(LinkedList *list, Position *element) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->element = element;
    node->next = NULL;

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

    list->size++;
}

// 从链表中移除第一个元素
Position *removeFirst_LinkedList(LinkedList *list) {
    if (list->size == 0)
        exit(-1);

    ListNode *removed = list->head;

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

    list->size--;

    return removed->element;
}

// m * n矩阵表示地图
int m, n;
int matrix[MAX_X][MAX_Y]; // 表示地图的矩阵

// 移动的四个方向的偏移量：上、下、左、右
int offsets[4][2] = {{-1, 0},
                     {1,  0},
                     {0,  -1},
                     {0,  1}};

// 广度优先搜索算法
int bfs() {
    if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
        return -1;
    }

    LinkedList *queue = new_LinkedList(); // BFS的队列

    Position *source = new_Position(0, 0);

    if (matrix[0][0] == -1) {
        source->initialFuel = 0;
        source->remainingFuel = 100;
        source->fuelAdded = 1;
    } else {
        source->initialFuel = matrix[0][0];
        source->remainingFuel = 0;
        source->fuelAdded = 0;
    }

    addLast_LinkedList(queue, source);

    int minInitialFuel[MAX_X][MAX_Y];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            minInitialFuel[i][j] = INT_MAX;
        }
    }

    int maxRemainingFuel[MAX_X][MAX_Y] = {0};

    minInitialFuel[0][0] = source->initialFuel;
    maxRemainingFuel[0][0] = source->remainingFuel;

    while (queue->size > 0) {
        Position *current = removeFirst_LinkedList(queue);

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

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

            int initialFuel = current->initialFuel;
            int remainingFuel = current->remainingFuel;
            int fuelAdded = current->fuelAdded;

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

            if (remainingFuel < 0) {
                if (fuelAdded) {
                    continue;
                } else {
                    initialFuel -= remainingFuel;
                    remainingFuel = 0;
                }
            }

            if (initialFuel > 100) {
                continue;
            }

            if (initialFuel > minInitialFuel[newX][newY]) {
                continue;
            }

            if (initialFuel < minInitialFuel[newX][newY] || remainingFuel > maxRemainingFuel[newX][newY]) {
                minInitialFuel[newX][newY] = initialFuel;
                maxRemainingFuel[newX][newY] = remainingFuel;

                Position *next = new_Position(newX, newY);
                next->initialFuel = initialFuel;
                next->remainingFuel = remainingFuel;
                next->fuelAdded = fuelAdded;

                addLast_LinkedList(queue, next);
            }
        }
    }

    if (minInitialFuel[m - 1][n - 1] == INT_MAX) {
        return -1;
    } else {
        return minInitialFuel[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;
}

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int m; // 矩阵的行数
    static int n; // 矩阵的列数
    static int[][] matrix; // 存储输入矩阵的二维数组

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in).useDelimiter("[,\n]"); // 使用逗号和换行符作为输入分隔符

        m = scanner.nextInt(); // 读取行数
        n = scanner.nextInt(); // 读取列数

        matrix = new int[m][n]; // 初始化矩阵
        int index = 0;
        while (index < m) { // 读取矩阵的元素
            int j = 0;
            while (j < n) {
                matrix[index][j] = scanner.nextInt();
                j++;
            }
            index++;
        }

        // 输出最小初始油量
        System.out.println(bfs());
    }

    // 节点类表示位置及其相关数据
    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() {
        // 处理起点或终点不可达的情况
        if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
            return -1;
        }

        LinkedList<Node> queue = new LinkedList<>(); // 队列用于BFS
        Node src = new Node(0, 0); // 创建起点

        // 根据起点状态初始化src节点
        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.add(src);

        // 初始化距离数组
        int[][] dist_init = new int[m][n]; // 存储到达每个位置需要的最小初始油量
        int i = 0;
        while (i < m) {
            int j = 0;
            while (j < n) {
                dist_init[i][j] = Integer.MAX_VALUE; // 初始距离设置为无穷大
                j++;
            }
            i++;
        }

        // 初始化剩余油量数组
        int[][] dist_remain = new int[m][n]; // 存储到达每个位置时的剩余油量

        // 设置起始位置的初始油量和剩余油量
        dist_init[0][0] = src.init;
        dist_remain[0][0] = src.remain;

        // 进行BFS
        while (!queue.isEmpty()) {
            Node cur = queue.removeFirst();

            // 定义可能的移动方向
            int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

            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 {
                    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;

                    queue.add(next);
                }
            }
        }

        // 如果无法到达终点，返回-1；否则返回最小初始油量
        return dist_init[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dist_init[m - 1][n - 1];
    }

    // 此函数不相关，仅作示例
    public static void irrelevantFunction() {
        System.out.println("这个函数做一些不相关的事情。");
    }
}