笔试时间：2024年09月11日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：最小距离和

每天早晨，环卫工人需要处理各个小区的生活垃圾，每个小区的生活垃圾由一队环卫工人负责运送到最近的垃圾回收站进行处理，求将所有小区垃圾送到垃圾回收站的最小距离和。假设小区和垃圾回收站都在都在一个m行 x n列的区域矩阵上，相邻点的距离为 1 ，只能上下左右移动；其中0表示垃圾处理站，1表示小区，2表示空白区域，-1表示障碍区域不可通行。区域内如果没有小区或者没有垃圾回收站，则最小距离和返回0。无法到达垃圾回收站的小区会单独处理，不计入本次距离和中。计算所有小区垃圾送到垃圾回收站的最小距离和。

解答要求：时间限制: C/C++ 1000ms, 其他语言：2000ms内存限制: C/C++ 256MB, 其他语言：512MB

输入描述

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

接下来的 m 行表示一个 m*n 的区域矩阵数组，每行的元素间以空格分隔，其中元素取值仅为-1（障碍区域）、0（垃圾处理站）、1（小区）、2（空白区域）。

输出描述

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

样例输入一

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 3 

0 -1 1 

1 -1 2

样例输出二

1

解释：

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

参考题解

BFS。将所有的垃圾站作为初始值加入到队列中，BFS，如此可以得到所有的小区距离垃圾站的最近的距离，最后累加所有的小区的距离垃圾站最小的距离即可。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> matrix(m, vector<int>(n));
    vector<vector<int>> dis(m, vector<int>(n, -1));
    queue<pair<int, int>> q;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 0) {
                q.push({i, j});
                dis[i][j] = 0;
            }
        }
    }

    int res = 0;
    int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();

        for (auto dir : directions) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] != -1 && dis[ni][nj] == -1) {
                dis[ni][nj] = dis[i][j] + 1;
                q.push({ni, nj});
            }
        }
    }

    res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1 && dis[i][j] != -1) {
                res += dis[i][j];
            }
        }
    }

    cout << res << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        int[][] matrix = new int[m][n];
        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dis[i], -1);
        }

        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
                if (matrix[i][j] == 0) {
                    q.offer(new int[]{i, j});
                    dis[i][j] = 0;
                }
            }
        }

        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int i = pos[0], j = pos[1];

            for (int[] dir : directions) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] != -1 && dis[ni][nj] == -1) {
                    dis[ni][nj] = dis[i][j] + 1;
                    q.offer(new int[]{ni, nj});
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && dis[i][j] != -1) {
                    res += dis[i][j];
                }
            }
        }

        System.out.println(res);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from collections import deque

m,n = map(int, input().split())
matrix = []
for _ in range(m): matrix.append([int(c) for c in input().split()])

q = deque()
dis = [[-1]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            q.append((i,j))
            dis[i][j] = 0

res = 0
while q:
    i,j = q.popleft()
    for ni,nj in ((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
        if 0<=ni<m and 0<=nj<n and matrix[ni][nj] != -1 and dis[ni][nj]==-1:
            dis[ni][nj] = dis[i][j] + 1
            q.append((ni,nj))

res