解题思路

• 将网格视作有向图的点，每个可燃单元格的燃烧时间就是它向外蔓延到相邻格子的“边权”。 若从 u=(x,y) 蔓延到相邻 v，则 time[v] = time[u] + burn(u)，其中 burn(u)=grids[x][y]。空地 0 不可被点燃也不能继续蔓延。
• 初始有多个起火点，均在时刻 0 被点燃，属于多源最短路问题。 用 Dijkstra（优先队列） 从所有起火点同时出发，维护每个格子被点燃的最早时刻 dist。
• 扩展仅在四联通方向（上/下/左/右）进行。最终答案为监控点 (a,b) 的 dist[a][b]；若该点为 0 或不可达，返回 -1。

要点：

• 多源：把所有起火点以距离 0 入堆。
• 边权取当前格子的燃烧时间，而非目标格子的时间。
• 监控点是空地时直接 -1。

复杂度分析

• 设网格大小为 m×n。 Dijkstra 时间复杂度 O(mn log(mn))，空间复杂度 O(mn)，满足题目规模（m,n ≤ 100）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
import heapq

# 功能函数：返回监控点最早着火时间
def earliest_fire_time(grids, fires, monitor):
    m, n = len(grids), len(grids[0])
    a, b = monitor
    # 监控点是空地，永远不会着火
    if grids[a][b] == 0:
        return -1

    INF = 10**18
    dist = [[INF] * n for _ in range(m)]
    pq = []

    # 多源起点：所有着火点时刻为0
    for x, y in fires:
        if 0 <= x < m and 0 <= y < n:
            dist[x][y] = 0
            heapq.heappush(pq, (0, x, y))

    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    while pq:
        t, x, y = heapq.heappop(pq)
        if t != dist[x][y]:
            continue
        # 当前格子为0则不能蔓延
        if grids[x][y] == 0:
            continue
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grids[nx][ny] != 0:
                nt = t + grids[x][y]  # 由当前格子燃烧完成后蔓延
                if nt < dist[nx][ny]:
                    dist[nx][ny] = nt
                    heapq.heappush(pq, (nt, nx, ny))

    return -1 if dist[a][b] >= INF else dist[a][b]

# 读一行网格（兼容“用空格分隔”或紧凑字符串如 031 的写法；默认每格为0~9）
def parse_row(line, n):
    line = line.strip()
    if " " in line:
        nums = list(map(int, line.split()))
        return nums
    # 紧凑无空格：逐字符解析
    return [int(c) for c in line][:n]

def main():
    data = sys.stdin.readline().strip()
    if not data:
        return
    m, n = map(int, data.split())
    grids = []
    for _ in range(m):
        line = sys.stdin.readline()
        row = parse_row(line, n)
        grids.append(row)

    # 读取着火点：一行若干整数，按 (x y) 成对出现
    fires_line = sys.stdin.readline().strip()
    fire_nums = list(map(int, fires_line.split())) if fires_line else []
    fires = [(fire_nums[i], fire_nums[i+1]) for i in range(0, len(fire_nums), 2)]

    # 读取监控点
    a, b = map(int, sys.stdin.readline().split())
    print(earliest_fire_time(grids, fires, (a, b)))

if __name__ == "__main__":
    main()

Java

// -*- coding: utf-8 -*-
import java.io.*;
import java.util.*;

// ACM 风格主类
public class Main {

    // 功能函数：Dijkstra 多源最短路
    static int earliestFireTime(int[][] g, List<int[]> fires, int a, int b) {
        int m = g.length, n = g[0].length;
        if (g[a][b] == 0) return -1; // 监控点为空地

        long INF = (long)1e18;
        long[][] dist = new long[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(dist[i], INF);

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o[0]));
        for (int[] f : fires) {
            int x = f[0], y = f[1];
            if (0 <= x && x < m && 0 <= y && y < n) {
                dist[x][y] = 0;
                pq.offer(new long[]{0, x, y});
            }
        }

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

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long t = cur[0];
            int x = (int)cur[1], y = (int)cur[2];
            if (t != dist[x][y]) continue;
            if (g[x][y] == 0) continue; // 空地不蔓延
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx][ny] != 0) {
                    long nt = t + g[x][y]; // 由当前格子蔓延
                    if (nt < dist[nx][ny]) {
                        dist[nx][ny] = nt;
                        pq.offer(new long[]{nt, nx, ny});
                    }
                }
            }
        }

        return dist[a][b] >= INF ? -1 : (int)dist[a][b];
    }

    // 解析一行网格（支持空格分隔或无空格如 031）
    static int[] parseRow(String line, int n) {
        line = line.trim();
        if (line.contains(" ")) {
            String[] ss = line.split("\\s+");
            int[] row = new int[n];
            for (int i = 0; i < n; i++) row[i] = Integer.parseInt(ss[i]);
            return row;
        } else {
            int[] row = new int[n];
            for (int i = 0; i < n && i < line.length(); i++) row[i] = line.charAt(i) - '0';
            return row;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] hw = br.readLine().trim().split("\\s+");
        int m = Integer.parseInt(hw[0]), n = Integer.parseInt(hw[1]);

        int[][] g = new int[m][n];
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            while (line != null && line.trim().isEmpty()) line = br.readLine();
            g[i] = parseRow(line, n);
        }

        // 着火点：按 (x y) 成对出现
        String firesLine = br.readLine();
        List<int[]> fires = new ArrayList<>();
        if (firesLine != null && firesLine.trim().length() > 0) {
            String[] ss = firesLine.trim().split("\\s+");
            for (int i = 0; i + 1 < ss.length; i += 2) {
                fires.add(new int[]{Integer.parseInt(ss[i]), Integer.parseInt(ss[i + 1])});
            }
        }

        String[] ab = br.readLine().trim().split("\\s+");
        int a = Integer.parseInt(ab[0]), b = Integer.parseInt(ab[1]);

        System.out.println(earliestFireTime(g, fires, a, b));
    }
}

C++

// -*- coding: utf-8 -*-
#include <bits/stdc++.h>
using namespace std;

// 功能函数：Dijkstra 多源最短路
int earliest_fire_time(const vector<vector<int>>& g,
                       const vector<pair<int,int>>& fires,
                       int a, int b) {
    int m = g.size(), n = g[0].size();
    if (g[a][b] == 0) return -1; // 监控点为空地

    const long long INF = (long long)4e18;
    vector<vector<long long>> dist(m, vector<long long>(n, INF));
    typedef tuple<long long,int,int> Node;
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    // for (auto [x, y] : fires)  ->  C++11 写法
    for (size_t i = 0; i < fires.size(); ++i) {
        int x = fires[i].first, y = fires[i].second;
        if (0 <= x && x < m && 0 <= y && y < n) {
            dist[x][y] = 0;
            pq.emplace(0LL, x, y);
        }
    }

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

    while (!pq.empty()) {
        // auto [t, x, y] = pq.top(); -> C++11 写法
        Node cur = pq.top(); pq.pop();
        long long t = std::get<0>(cur);
        int x = std::get<1>(cur);
        int y = std::get<2>(cur);

        if (t != dist[x][y]) continue;
        if (g[x][y] == 0) continue; // 空地不蔓延
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx>=0 && nx<m && ny>=0 && ny<n && g[nx][ny] != 0) {
                long long nt = t + g[x][y]; // 由当前格子蔓延
                if (nt < dist[nx][ny]) {
                    dist[nx][ny] = nt;
                    pq.emplace(nt, nx, ny);
                }
            }
        }
    }
    return dist[a][b] >= INF ? -1 : (int)dist[a][b];
}

// 解析一行网格：支持空格分隔或紧凑字符串如 031（默认每格0~9）
vector<int> parse_row(const string& line, int n) {
    vector<int> row;
    string s = line;
    if (s.find(' ') != string::npos || s.find('\t') != string::npos) {
        istringstream iss(s);
        int x;
        while (iss >> x) row.push_back(x);
    } else {
        for (size_t i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (!isspace((unsigned char)c)) row.push_back(c - '0');
        }
    }
    if ((int)row.size() < n) row.resize(n, 0);   // 防越界，缺的补0
    else if ((int)row.size() > n) row.resize(n);
    return row;
}

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

    int m, n;
    if (!(cin >> m >> n)) return 0;
    string dummy;
    getline(cin, dummy); // 吃掉行尾

    vector<vector<int>> g(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        string line;
        getline(cin, line);
        while (!line.empty() &&
               all_of(line.begin(), line.end(),
                      [](char c){ return isspace((unsigned char)c); })) {
            getline(cin, line);
        }
        vector<int> row = parse_row(line, n);
        for (int j = 0; j < n; ++j) g[i][j] = row[j];
    }

    // 读取着火点：一行若干整数，按 (x y) 成对
    string firesLine;
    getline(cin, firesLine);
    while (!firesLine.empty() &&
           all_of(firesLine.begin(), firesLine.end(),
                  [](char c){ return isspace((unsigned char)c); })) {
        getline(cin, firesLine);
    }
    istringstream iss(firesLine);
    vector<int> fs; int val;
    while (iss >> val) fs.push_back(val);
    vector<pair<int,int>> fires;
    for (size_t i = 0; i + 1 < fs.size(); i += 2) fires.push_back(make_pair(fs[i], fs[i+1]));

    // 读取监控点
    string abLine;
    getline(cin, abLine);
    istringstream iss2(abLine);
    int a, b; iss2 >> a >> b;

    cout << earliest_fire_time(g, fires, a, b) << "\n";
    return 0;
}

题目内容

你负责开发一个火灾监控预警系统，在二维网格中，每个网格可以是空地 $(0)$ 或不同类型的可燃物( $1$ 到 $k$ 的正整数，数值对应燃烧时间)。火势从初始着火点开始，蔓延规则为:可燃物被点燃后，需经过其燃烧时间才能向四周蔓延。求监控点被点燃的最早时间，若无法被点燃或监控点是空地，返回 $-1$ 。

输入描述

输入内容:

1.二维监控区域 $grids$，其空间 $size$ 为 $m×n(0<m<=100,0<n<=100)$，如 $4×3$ 区域空间 $[[0,1,2],[1,2,1],[1,1,1],[1,0,1]]$，$0$ 表示空地，其余表示可燃物燃烧时间;

2.着火点坐标 $fires$，由多个二维坐标点组成 $[x,y](0<=x<m,0<=y<n)$，着火点数量少于 $5$ ，如: $[[0,0],[0,1]]$

3.监控点坐标 $monitor$ ,单个二维坐标点 $[a,b](0<=a<m,0<=b<n)$，如: $[2,2]$

输入格式:

第 $1$ 行:矩阵 $size$，$m$ $n$，用空格分隔

第 $2-m+1$ 行:二维矩阵内容，每行代表矩阵的一行数据，每个数据空格分隔

第 $m+2$ 行:着火点坐标，含多个着火点，用空格分隔，$0$ $0$ $2$ $0$ 表示 $2$ 个着火点 $[0,0]$ 与 $[2,0]$

第 $m+3$ 行:监控点坐标,单个着火点，用空格分隔

输出描述

输出:几分钟后火情蔓延至监控坐标 $monitor$ ,不会着火返回 $-1$

样例1

输入

3 3
1 0 0
0 3 1
1 0 2
0 0 2 0
2 2

输出

-1

说明

$[2,0]$ 坐标位置的着火点无法蔓延

$[0,0]$ 坐标位置的着火点无法蔓延

$[2,2]$ 坐标不会着火，返回 $-1$

样例2

输入

3 3
1 2 0
0 3 1
1 0 2
0 0 2 0
2 2

输出

7

说明

$[2,0]$ 坐标位置的着火点无法蔓延

$[0,0]$ 坐标位置的着火点 $->[0,1]$ 花费时间 $1$

$->[1,1]$ 花费时间 $2$

$->[1,2]$ 花费时间 $3$

$->[2,2]$ 花费时间 $1$

一共花费时间 $7$