题面解释:

在一个由$m$行$n$列的区域矩阵中，环卫工人需要将小区的生活垃圾送到最近的垃圾回收站。矩阵中的元素取值为0（垃圾处理站）、1（小区）、2（空白区域）和-1（障碍区域），相邻点的距离为$1$，且只能上下左右移动。要求计算所有小区垃圾送到垃圾回收站的最小距离和。如果矩阵中没有小区或垃圾处理站，则返回$0$。无法到达垃圾回收站的小区将不计入距离和中。输入包括第一行的两个整数$m$和$n$，表示区域矩阵的行数和列数，接下来的$m$行表示区域矩阵。输出为一个整数，表示计算得出的最小距离和。

思路：多源bfs

将所有垃圾站的距离初始化为0，并加入队列中。用广度优先搜索算法逐层向外扩展，并用一个额外数组记录到达每个点的最短距离。如果一个点有值，说明某一个垃圾站离该点更近，则不在使用当前点进行该方向的扩展。

最后扫描所有小区，累加它们的值即可。不可到达的小区值为0。

题解

在给定的$m \times n$的区域矩阵中，我们需要将小区的生活垃圾送到最近的垃圾回收站。矩阵中的元素可以是垃圾站（0），小区（1），空白区域（2）和障碍区域（-1）。相邻点的距离为1，我们只能在上下左右四个方向移动。

为了计算所有小区到垃圾回收站的最小距离和，我们采用广度优先搜索（BFS）算法。BFS是一种层次遍历的搜索算法，可以有效地找到每个点到起始点的最短路径。

具体步骤如下：

1. 初始化：创建一个距离矩阵d，用-1表示不可到达，垃圾站的距离初始化为0，并将所有垃圾站的位置加入队列。
2. 广度优先搜索：从队列中的垃圾站开始，逐层向外扩展，更新每个可到达点的最短距离。如果一个点的距离已经被更新，表示该点到达的距离更短，则不再更新。
3. 计算总和：遍历所有小区，累加它们的距离，如果某个小区不可达则其值视为0。

代码

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;  // 程序结束
}

题目内容

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

假设小区和垃圾回收站都在都在一个$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$。