本题为2024年9月11日华为机考原题

华为机考的介绍点击这里

题目内容

每天早晨，环卫工人需要处理各个小区的生活垃圾，每个小区的生活垃圾由一队坏卫工人负责运送到最近的垃圾回收站进行处理，求将所有小区垃圾送到垃圾回收站的最小距离和。

假设小区和垃圾回收站都在都在一个$m$行$x$ $n$列的区域矩阵上，相邻点的距离为$1$，只能上下左右移动;其中$0$表示垃圾处理站，$1$表示小区，$2$表示空白区域，$-1$表示障碍区域不可通行。

区域内如果没有小区或者没有垃圾回收站，则最小距离和返回$0$。

无法到达垃圾回收站的小区会单独处理，不计入本次距离和中。

计算所有小区垃圾送到垃圾回收站的最小距离和。

输入描述

第一行为两个数字$m$和$n$的和，表示区域矩阵的行数和列数，中间使用空格分隔，$m$和$n$的范围均为$[1,300]$。

接下来的$m$行表示一个$m×n$的区域矩阵数组，每行的元素间以空格分隔，其中元素取值仅为$-1$(障碍区域)、

$0$(垃圾处理站)、$1$(小区)、$2$(空白区域)。

输出描述

一个整数，表示所计算的最小距离和。

样例1

输入

4 4
1 2 -1 1
2 0 2 0
2 2 -1 2
1 2 1 1

输出

11

说明

如图所示，位置$[0,0]、[0,3]、[3,0]、[3,2]、[3,3]$是小区，位置$[1,1]、[1,3]$是垃圾站，位置$[0,2]、[2,2]$是

障碍，无法通行，$5$个小区，$2$个垃圾站，小区到垃圾站的最小路径是$2+3+1+3+2=11$。

对于位置$[3,2]$的小区，可以将垃圾运送到垃圾站$[1,1]$、$[1,3]$，两者的距离是一样的。

题解图示仅以到$[1,3]$垃圾站进行说明。

样例2

输入

2 3
0 -1 1
1 -1 2

输出

1

说明

如图所示，位置$[0,2]、[1,0]$小区，位置$[0,0]$是垃圾站，位置$[0,1]、[1,1]$是障碍，无法通行，$2$个小区，$1$个垃圾站，小区到垃圾站的最小路径是$1+0=1$。

题目大意：

在一个由 m 行 n 列的区域矩阵中，环卫工人需要将小区的生活垃圾送到最近的垃圾回收站。矩阵中的元素取值为：

• 0：垃圾处理站
• 1：小区
• 2：空白区域
• -1：障碍区域

相邻点的距离为 1，且只能上下左右移动。要求计算所有小区垃圾送到垃圾回收站的最小距离和。如果矩阵中没有小区或垃圾回收站，则返回 0。无法到达垃圾回收站的小区将不计入距离和中。

思路：多源 BFS

多源 BFS（广度优先搜索） 是一种从多个起始节点同时进行广度优先搜索的策略。与传统的单源 BFS 仅从一个起始点出发进行广度优先遍历不同，多源 BFS 会从多个起始点同时开始 BFS，逐层扩展。

跟前面三个BFS题的区别也就是多了些起点，多源BFS从多个源节点同时出发，计算从多个起点到目标节点的最短路径，适用于多个目标同时进行计算的情况,在初始化的时候就要比单源BFS添加更多的起点。

1. 问题分析：

   • 题目要求计算所有小区到垃圾回收站的最短距离和。
   • 这里很明显是需要多个目标同时进行计算，那么我们考虑多源BFS
   • 对于每个垃圾回收站，开始进行 BFS 传播，直到所有的节点都被访问过或更新过最短距离。

2. 关键点分析：

   • 我们将所有垃圾回收站的位置作为起点，进行多源 BFS。
   • 每个小区到最近垃圾回收站的最短距离可以通过 BFS 逐层扩展得到。
   • 对于无法到达垃圾回收站的小区，不计入距离和。

3. 代码步骤：

   • 初始化：将所有垃圾回收站的距离设置为 0，并将它们加入队列。
   • BFS 扩展：从垃圾回收站开始，逐步向外扩展，更新每个小区的最短距离。
   • 最后遍历矩阵，将所有小区的最短距离求和。

理解题意有多个起点的情况，其实难度跟前面BFS难度差不多最后贴上我们的ac代码给大家参考

代码实现

Python 代码：

from collections import deque

# 初始化读取输入数据
def init():
    n, m = map(int, input().split())  # 读取行数和列数
    a = [list(map(int, input().split())) for _ in range(n)]  # 读取矩阵，表示小区与垃圾站位置
    return n, m, a

def solve(n, m, a):
    # 初始化一个与原矩阵相同大小的矩阵，用于存储每个点的距离
    b = [[0] * m for _ in range(n)]
    q = deque()

    # 初始化队列，将所有垃圾站(值为0)的位置加入队列
    for i in range(n):
        for j in range(m):
            if a[i][j] == 0:
                q.append((i, j, 0))  # (x坐标, y坐标, 当前距离)

    # 定义四个方向的移动
    dx = [0, 0, -1, 1]  # 左右
    dy = [1, -1, 0, 0]  # 上下

    # BFS 广度优先遍历更新距离
    while q:
        x, y, now = q.popleft()  # 当前点的坐标及距离
        for i in range(4):  # 遍历四个方向
            nx, ny = x + dx[i], y + dy[i]
            # 检查新点是否在边界内
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 如果该点已经被更新，则跳过
            if b[nx][ny] != 0:
                continue
            # 如果该点是障碍物(值为-1)，则跳过
            if a[nx][ny] == -1:
                continue
            # 更新距离矩阵
            b[nx][ny] = now + 1
            q.append((nx, ny, now + 1))  # 将新点加入队列

    # 计算所有小区到垃圾站的最短距离总和
    total_sum = 0
    for i in range(n):
        for j in range(m):
            if a[i][j] == 1:  # 只对小区(值为1)计算距离
                total_sum += b[i][j]

    print(total_sum)  # 输出结果

# 主函数
if __name__ == "__main__":
    n, m, a = init()
    solve(n, m, a)

Java 代码：

import java.util.*;

public class Main {
    // 定义全局变量矩阵和距离矩阵
    public static int[][] mp; // 存储输入矩阵，表示小区和垃圾站的位置
    public static int[][] d;  // 存储每个点到最近垃圾站的最短距离
    public static int n, m;   // 行数和列数

    // 计算所有小区到垃圾站的最短距离之和
    public static int solve() {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 累加所有小区(值为1)的距离
                if (mp[i][j] == 1 && d[i][j] != -1) {
                    ans += d[i][j];
                }
            }
        }
        return ans;  // 返回总和
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();  // 读取行数
        m = sc.nextInt();  // 读取列数
        mp = new int[n][m];
        d = new int[n][m];

        // 初始化输入矩阵和距离矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mp[i][j] = sc.nextInt();  // 读取矩阵元素
                d[i][j] = -1;  // 初始化距离为 -1
            }
        }

        // BFS 实现
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mp[i][j] == 0) {  // 垃圾站
                    queue.offer(new int[]{i, j});
                    d[i][j] = 0;  // 垃圾站的距离为 0
                }
            }
        }

        // 定义四个方向的移动（右、左、下、上）
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        // 执行 BFS
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny] == -1 && mp[nx][ny] != -1) {
                    d[nx][ny] = d[x][y] + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        // 输出结果
        System.out.println(solve());
    }
}

C++ 代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;  // 定义全局变量行数和列数
vector<vector<int>> mp;  // 输入矩阵，存储区域信息
vector<vector<int>> d;   // 记录到每个点的最短距离，初始化为-1表示不可达

// 计算所有小区到垃圾站的最短距离之和
int solve() {
    int ans = 0;  // 初始化答案
    for (int i = 0; i < n; i++) {  // 遍历每一行
        for (int j = 0; j < m; j++) {  // 遍历每一列
            if (mp[i][j] == 1 && d[i][j] != -1) {  // 如果是小区且可达
                ans += d[i][j];  // 累加到总距离
            }
        }
    }
    return ans;  // 返回计算的总和
}

// 广度优先搜索更新距离矩阵
void bfs() {
    queue<pair<int, int>> q;  // 创建队列用于存储位置
    // 将所有垃圾站(值为0)的位置加入队列，并初始化它们的距离为0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 0) {  // 找到垃圾站
                q.push({i, j});  // 加入队列
                d[i][j] = 0;  // 垃圾站的距离设为0
            }
        }
    }

    // 定义四个方向的移动（右、左、下、上）
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    
    // 开始BFS遍历
    while (!q.empty()) {  // 当队列不为空时
        auto current = q.front();  // 获取队头元素
        q.pop();  // 弹出队头元素
        int x = current.first;  // 当前x坐标
        int y = current.second;  // 当前y坐标

        for (int i = 0; i < 4; i++) {  // 遍历四个方向
            int nx = x + dx[i];  // 计算新x坐标
            int ny = y + dy[i];  // 计算新y坐标
            // 检查新点是否在边界内并且没有被访问过且不是障碍
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny] == -1 && mp[nx][ny] != -1) {
                d[nx][ny] = d[x][y] + 1;  // 更新新点的距离
                q.push({nx, ny});  // 将新点加入队列
            }
        }
    }
}

int main() {
    cin >> n >> m;  // 读取行数和列数
    mp.resize(n, vector<int>(m));  // 初始化输入矩阵
    d.resize(n, vector<int>(m, -1));  // 初始化距离矩阵为-1

    // 读取输入矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];  // 输入区域信息
        }
    }

    // 执行广度优先搜索更新最短距离
    bfs();
    // 输出结果，即所有小区到垃圾站的最小距离和
    cout << solve() << endl;

    return 0;  // 程序结束
}