解题思路

本题本质是一个网格图上的最短路问题。由于每个工作站都可以同时、无限量地派出工作人员，并且移动代价一致（上下左右、每步 1 分钟），因此从所有工作站同时出发，在可通行的格子（0、1、3）上进行多源 BFS（图论），即可一次性得到每个位置到最近工作站的最短时间。

• 将所有值为 3 的工作站位置同时入队，距离置为 0。

• 进行 BFS 扩展：只能走到非障碍（不为 2）且未访问过的位置，邻居距离为当前距离 + 1。

• BFS 完成后：

  • 在所有基站位置（值为 1）中，取其被访问到的距离的最大值，这就是完成所有可维护（可达）基站所需的最小时间（最后到达的那一个决定总耗时）。
  • 若不存在任何一个可达的基站（即所有 1 的位置都未被访问），按题意输出 -1。
  • 注意：题面要求“完成所有可维护基站”，因此无法到达的基站不计入；只有在“所有基站都不可达”时才输出 -1。

该方法一次 BFS 即可获得答案，简洁高效。无需贪心、动态规划或二分等额外技巧；如果用二分时间 + 可达性检查也能做，但属于多余开销。

复杂度分析

• 设网格大小为 m × m，节点数 N = m^2。
• 时间复杂度：BFS 仅遍历每个格子及边常数次，O(N)。
• 空间复杂度：距离数组/访问标记与队列最多存放 N 个元素，O(N)。
• 在 m < 1000 的范围内，该复杂度完全可行。

代码实现

Python

import sys
import ast
from collections import deque

def min_time_to_maintain(grid, m):
    # 四个方向
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]
    # 距离数组，-1 表示未访问
    dist = [[-1]*m for _ in range(m)]
    q = deque()

    # 收集所有工作站作为多源起点
    for i in range(m):
        for j in range(m):
            if grid[i][j] == 3:
                dist[i][j] = 0
                q.append((i, j))

    # BFS
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            # 越界检查 + 非障碍 + 未访问
            if 0 <= nx < m and 0 <= ny < m and grid[nx][ny] != 2 and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    # 统计所有可达基站的最大距离
    ans = -1
    has_base = False
    for i in range(m):
        for j in range(m):
            if grid[i][j] == 1:
                has_base = True
                if dist[i][j] != -1:
                    ans = max(ans, dist[i][j])

    # 如果存在基站但没有任何可达的基站，则返回-1；否则返回最大距离
    return -1 if ans == -1 else ans

def main():
    data = sys.stdin.read().strip().splitlines()
    m = int(data[0].strip())
    grid = []
    # Python 优先使用 literal_eval：将每行空格分隔数字转成列表
    # 这里通过替换空格为逗号并加上方括号，使其成为合法的Python列表字面量
    for i in range(1, m + 1):
        line = data[i].strip()
        row = list(map(int, ast.literal_eval('[' + line.replace(' ', ',') + ']')))
        grid.append(row)

    print(min_time_to_maintain(grid, m))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    // 外部函数：计算最小时间
    static int minTimeToMaintain(int[][] grid, int m) {
        int[][] dist = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) dist[i][j] = -1;
        }

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

        // 所有工作站作为多源起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 3) {
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }

        // BFS
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < m && ny >= 0 && ny < m) {
                    if (grid[nx][ny] != 2 && dist[nx][ny] == -1) { // 非障碍且未访问
                        dist[nx][ny] = dist[x][y] + 1;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        // 统计所有可达基站的最大距离
        int ans = -1;
        boolean hasBase = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    hasBase = true;
                    if (dist[i][j] != -1) {
                        ans = Math.max(ans, dist[i][j]);
                    }
                }
            }
        }

        return ans == -1 ? -1 : ans;
    }

    public static void main(String[] args) throws IOException {
        // 依据数据规模使用 BufferedReader + StringTokenizer（比 Scanner 更稳）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().trim());
        int[][] grid = new int[m][m];

        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line, " ");
            for (int j = 0; j < m; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = minTimeToMaintain(grid, m);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int minTimeToMaintain(const vector<vector<int>>& grid, int m) {
    // 四方向数组
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    // 距离数组，-1表示未访问
    vector<vector<int>> dist(m, vector<int>(m, -1));
    queue<pair<int,int>> q;

    // 多源起点：所有工作站位置
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 3) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    // BFS
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 越界检查 + 非障碍 + 未访问
            if (nx >= 0 && nx < m && ny >= 0 && ny < m) {
                if (grid[nx][ny] != 2 && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    // 统计可达基站的最大距离
    int ans = -1;
    bool hasBase = false;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1) {
                hasBase = true;
                if (dist[i][j] != -1) {
                    ans = max(ans, dist[i][j]);
                }
            }
        }
    }

    return (ans == -1 ? -1 : ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    if (!(cin >> m)) return 0;
    vector<vector<int>> grid(m, vector<int>(m, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j]; // 空格分隔读取
        }
    }

    int ans = minTimeToMaintain(grid, m);
    cout << ans << "\n";
    return 0;
}

题目内容

在大小为 $m*m$ 的城市中分布着一些基站，这些基站需要进行例行的维护工作。维护工作由多个工作站中的工作人员来完成。工作人员可以从工作站出发，只能上下左右移动，每走一次消耗时间 $1$ 分钟，忽略维护的手机开销（到达即完成维护）。

城市中有一些工作人员无法跨越的障碍，遇到阻碍需要绕过，假定每个工作站中工作人员数量不限。请输出最少需要多少时间，工作人员可以维护完所有的基站。请输出最少多少制间完成所有可维护基站的维护，如果出现所有基站都无法维护的情况，请返回 $-1$ 。不考虑整个城市中都没有基站的情况，用例保证一定有需要维护的基站。

地图中，$0$ 代表空地，可以穿过。$1$ 代表基站，也可以穿过。$2$ 代表障碍，无法穿过。$3$ 代表工作站。

输入描述

第一行给出一个正整数 $m(0<1000)$ 。第二行开始到第 $m+1$ 行，每一行 $m$ 个数字，代表地图中第 $1$ 到 第 $m$ 行的空地、基站、障碍、工作站等信息。

输出描述

请输出维护花费的最小时间

样例1

输入

3
3 2 3
2 1 2
1 0 0

输出

-1

说明

位置 $[0,0]$ 和 $[0,2]$ 的工作站都被障碍完全阻隔无法派出工作人员，所有基站都无法维护。

样例2

输入

3
3 1 0
1 3 0
1 0 1

输出

2

说明

工作站位置在地图的 $[0,0]$ 和 $[1,1]$ ，工作站同时派出工作人员维护的位置在 $[0,1]、[1,0]、[2,0]、[2,2]$ 位置的 $4$ 个基站，工作站 $[1,1]$ 的工作人员维护 $[2,2]$ 基站需要走 $2$ 步。

工作站 $[0,0]$ 的工作人员派出 $3$ 名工作人员，维护位置在 $[0,1]、[1,0]、[2,0]$ 的 $3$ 个基站，最多需要走 $2$ 步。维护所有基站花费的最小时间是 $2$ 分钟。