#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    vector<vector<int>> grid(m,vector<int>(n,0));
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) cin>>grid[i][j];
    // for(int i=0;i<m;++i) for(int j=0;j<n;++j) cout<<grid[i][j]<<" ";
    vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    //多到多的扩散 这里选择从垃圾站扩散到小区？为什么？
    //如果假设从小区扩散到垃圾站，如果多个小区有相同的路径，
    //    每个格子可能就需要遍历多次，那么就会复杂度就会随着小区的数量++。
    //如果从垃圾站到小区，那么沿路的格子都可以屏蔽掉（某条路径先到了该格，其他路径就不需要来了，都没有第一条来的时间快了），
    //    防止重复走，每个格子只需要遍历一次即可。
    queue<pair<int,int>> que;
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(grid[i][j] == 0) que.push({i,j});
    int step = 1, sum = 0;
    while(!que.empty())
    {
        int size = que.size();
        for(int i=0;i<size;++i)
        {
            pair<int,int> cur = que.front();
            int cur_i = cur.first, cur_j = cur.second;
            grid[cur_i][cur_j] = -1;
            for(const pair<int,int>& dir:dirs)
            {
                int new_i = cur_i + dir.first, new_j = cur_j + dir.second;
                if(new_i>=0 && new_i<m && new_j>=0 && new_j < n && grid[new_i][new_j] != -1)
                {
                    que.push({new_i,new_j});
                    if(grid[new_i][new_j] == 1) sum += step;
                    grid[new_i][new_j] = -1;
                }
            }
            que.pop();
        }
        ++step;
    }
    cout<<sum;
    return 0;
}

from collections import deque

n , m = map(int , input().split())  # 读取行数和列数
g = [list(map(int,input().split())) for _ in range(n)]
dis = [[0]*m for _ in range(n)]
q = deque()
for i in range(n):
    for j in range(m):
        if g[i][j]==0:
            q.append((i,j,0))
dx = [0,0,1,-1]
dy = [1,-1,0,0]

while q:
    x,y,now = q.popleft()
    for i in range(4):
        new_x = x+dx[i]
        new_y = y+dy[i]
        if 0<=new_x<n and 0<=new_y<m and dis[new_x][new_y]==0 and g[new_x][new_y]!=-1:
            dis[new_x][new_y]=now+1
            q.append((new_x,new_y,dis[new_x][new_y])) 

res = 0
for i in range(n):
    for j in range(m):
        if g[i][j]==1:
            res+=dis[i][j]
print(res)

from collections import deque
m,n = map(int, input().split(' '))
a = [list(map(int, input().split())) for _ in range(n)]

def idx_valid(x,y,m,n):
    row = (x>=0 and x<m)
    col = (y>=0 and y<n)
    return (row and col)
def bfs_single(m,n,a, i, j):
    # 多个start，多个target
    # 如果简化为单start多target,找到一个target就返回
    dx, dy = [0,0,1,-1],[1,-1,0,0]
    q = deque()
    visited = set()
    pth = 0
    q.append((i,j))
    visited.add((i,j))
    # while控制往深层遍历，for控制同层遍历
    while q:
        pth += 1
        size = len(q)
        for _ in range(size):
            idx = q.popleft()
            x,y = idx[0], idx[1]
            for i in range(4):
                x_, y_ = x+dx[i], y+dy[i]
                if idx_valid(x_, y_, m, n):
                    if a[x_][y_]==-1: continue
                    elif a[x_][y_]==0:
                        return pth
                    else:
                        if (x_, y_) not in visited:
                            q.append((x_, y_))
                            visited.add((x_, y_))
    return 0

xiaoqu = []
for i in range(m):
    for j in range(n):
        if a[i][j]==1: xiaoqu.append((i,j))

cum = 0
for x in xiaoqu:
    cum += bfs_single(m,n,a,x[0],x[1])
print(cum)

public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int m = in.nextInt();
            int n = in.nextInt();
            int[][] matrix = new int[m][n];
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    matrix[i][j] = in.nextInt();
                }
            }
            minDistance(matrix, m, n);
        }
    }

    /**
     * 一开始用正常的bfs思路做后面十个用例一直超时
     * 看了题解以后才知道可以多源bfs，同时扩展，可以避免很多重复搜索和最近距离更新
     * @param matrix
     * @param m
     * @param n
     */
    private static void minDistance(int[][] matrix, int m, int n){
        Queue<int[]> queue = new LinkedList<>();
        int[][] flag = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    queue.add(new int[]{i, j, 0});
                }
            }
        }
        while(!queue.isEmpty()){
            int[] temp = queue.poll();
            int row = temp[0]; //行
            int col = temp[1]; //列
            int count = temp[2]; // 距离垃圾站的距离
            //判断index是否合法，以及是否该节点被访问过
            // 如果被优先访问，则一定更近或者相等距离
            if(row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length
                    && flag[row][col] == 0){
                if(matrix[row][col] == 1){
                    flag[row][col] = count; // 小区的点上直接更新距离
                } else if (matrix[row][col] == -1){
                    continue;
                } else {
                    flag[row][col] = 1; // 标记已访问
                }
                queue.add(new int[]{row + 1, col, count + 1});
                queue.add(new int[]{row - 1, col, count + 1});
                queue.add(new int[]{row, col + 1, count + 1});
                queue.add(new int[]{row, col - 1, count + 1});
            }
        }
        int sum = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 1){
                    sum = sum + flag[i][j];
                }
            }
        }
        System.out.println(sum);
    }

题面解释:

在一个由$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

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