题目内容

塔子哥有一些神奇的镜子，这些镜子能够吸收光芒，并在一定时间后对光芒进行散射。

塔子哥的镜子分为一级镜和二级镜，一级镜的散射速度比较快， $1ms$ 就可以将光芒向上下左右四个方向散射过去，而二级镜则需要 $2ms$ 。

塔子哥将这些镜子放在了一个二维矩阵中，且每个镜子的坐标均为整数。

现在，塔子哥给某一个镜子一道光芒，他想知道，最早什么时候所有镜子都能够吸收到光芒？

注：矩阵的下标从0开始

输入描述

矩阵的列数 $n(n\le500)$

矩阵的行数 $m(n\le500)$

最初获得光芒的镜子的坐标 $(i,j)$

接下来 $m$ 行，每行 $n$ 个数字，代表该位置镜子的等级:

如果为 $0$ ，表示该位置是一堵密不透光的墙，它足以抵挡所有的光线。

如果为 $1$ ，表示该位置的镜子散射耗时1ms

如果为 $2$ ，表示该位置的镜子散射耗时2ms

输出描述

一个数字代表最小时间。如果有镜子不能够吸收到光芒，那么输出-1

样例

输入

输出

题面描述

塔子哥有一些神奇的镜子，能够吸收光芒并在一定时间后散射。镜子分为一级镜和二级镜，一级镜散射光芒需1毫秒，而二级镜需2毫秒。塔子哥将这些镜子放在一个二维矩阵中，并给定光源镜子的坐标。输入包括矩阵的行列数、光源坐标以及每个位置的镜子等级（0为墙体，1为一级镜，2为二级镜）。输出为所有镜子最早吸收到光芒的时间，若有镜子无法吸收到光芒则输出-1。

思路：Dijkstra

目标是找到所有镜子接收到光芒的最早时间。因此可以想到单源最短路算法：dijkstra

首先，我们需要创建一个二维数组 dis 来存储每个镜子接收到光芒的时间，初始值设为一个较大的数。同时，我们需要一个二维数组 bk 来标记每个镜子是否已经接收到光芒，初始值设为 False。

然后，我们使用优先队列 q，并将初始镜子的坐标和接收到光芒的时间（设为 0）加入队列。

接下来，我们进行Dijkstra算法。在每一步，我们取出队列中时间最早的镜子，然后更新其四个方向的镜子的接收时间。如果新的接收时间比当前的接收时间早，我们就更新接收时间，并将新的镜子加入队列。

最后，我们遍历所有的镜子，找出接收到光芒的最晚时间，即为所有镜子都能够吸收到光芒的最早时间。

算法步骤：

初始化：
- 创建一个二维数组 dist 来存储每个镜子接收到光芒的时间，初始值设为一个较大的数（INT_MAX / 2），以避免溢出。
- 创建一个二维布尔数组 visited 来标记每个镜子是否已经接收到光芒，初始值设为 false。
- 使用优先队列 pq 存储每个镜子的坐标和接收到光芒的时间，并将初始镜子的坐标和时间（0）加入队列。
Dijkstra算法：
- 在每一步中，从队列中取出时间最早的镜子，检查其四个方向（上下左右）的邻接镜子。
- 如果邻接镜子的接收时间比当前的接收时间早，则更新接收时间，并将邻接镜子加入队列。
- 继续这个过程，直到所有可达的镜子都接收到光芒或队列为空。
结果计算：
- 遍历所有镜子，找出接收到光芒的最晚时间，即为所有镜子都能够吸收到光芒的最早时间。如果有镜子仍未接收到光芒，则返回-1。

时间复杂度

$O(nmlog(nm))$

代码

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
    vector<int> directions{-1, 0, 1, 0, -1}; // 四个方向的移动向量
    int n, m;
    cin >> n; // 矩阵的列数
    cin >> m; // 矩阵的行数

    int si, sj;
    cin >> si >> sj; // 初始光源镜子的坐标

    int left = 0; // 镜子的数量
    vector<vector<int>> grid(n, vector<int>(m, 0)); // 存储镜子的等级
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j]; // 输入每个位置的镜子等级
            if (grid[i][j] > 0) left++; // 统计可接收光芒的镜子数量
        }
    }

    vector<vector<int>> dist(n, vector<int>(m, INT_MAX / 2)); // dist数组，用于存储到达每个镜子的时间
    vector<vector<bool>> visited(n, vector<bool>(m, false)); // visited数组，标记镜子是否接收到光芒
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; // 优先队列，存储<时间, 镜子坐标>

    pq.push({0, si, sj}); // 将初始镜子加入队列
    dist[si][sj] = 0; // 初始镜子的接收时间为0
    left--; // 初始镜子已接收到光芒

    while (!pq.empty()) {
        auto item = pq.top(); // 取出时间最早的镜子
        int d = item[0], i = item[1], j = item[2];
        pq.pop();
        if (visited[i][j]) continue; // 如果该镜子已接收到光芒，跳过

        visited[i][j] = true; // 标记该镜子已接收到光芒

        // 检查四个方向
        for (int k = 0; k < 4; k++) {
            int nx = i + directions[k]; // 新的x坐标
            int ny = j + directions[k + 1]; // 新的y坐标
            // 判断新坐标是否在有效范围内，且为镜子
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] > 0 && dist[nx][ny] > d + grid[i][j] && !visited[nx][ny]) {
                if (dist[nx][ny] >= INT_MAX / 2) // 刚到达了一个镜子
                    left--; // 剩余可接收光芒的镜子数量减一
                dist[nx][ny] = d + grid[i][j]; // 更新接收时间
                pq.push({dist[nx][ny], nx, ny}); // 将新镜子加入队列
            } 
        }
        if (left == 0) break; // 如果所有镜子都接收到光芒，结束
    }

    int stamp = 0; // 存储接收到光芒的最晚时间
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] > 0) // 只检查镜子
                stamp = max(stamp, dist[i][j]); // 更新最晚时间
        }
    }
    
    if (stamp >= INT_MAX / 2) {
        stamp = -1; // 如果未能接收到光芒，返回-1
    }
    cout << stamp << endl; // 输出结果

    return 0;
}

python代码

import heapq  # 导入堆队列算法库，用于实现优先队列

# 输入矩阵的行数和列数
m = int(input())  # 行数
n = int(input())  # 列数

# 输入光源镜子的起始坐标
s, e = map(int, input().split())

# 输入矩阵数据，表示镜子的等级
a = [list(map(int, input().split())) for i in range(n)]

# 初始化距离数组，设为一个很大的数（模拟无穷大）
dis = [[10**9] * m for i in range(n)]
# 初始化访问标记数组，标记镜子是否已经接收到光芒
bk = [[False] * m for i in range(n)]

# 定义四个方向的移动向量（上下左右）
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 设置初始光源的接收时间为0，并将其加入优先队列
dis[s][e] = 0
q = []
heapq.heappush(q, [0, s, e])  # 将初始镜子的坐标和时间加入队列

# Dijkstra算法的主循环
while len(q) > 0:
    # 从队列中取出时间最早的镜子
    u = q.pop(0)  # 弹出优先队列中的最小元素
    u = u[1:]     # 获取镜子的坐标
    if bk[u[0]][u[1]]:  # 如果该镜子已接收到光芒，跳过
        continue
    bk[u[0]][u[1]] = True  # 标记该镜子已接收到光芒

    # 遍历四个方向的邻接镜子
    for d in range(4):
        x = u[0] + dx[d]  # 新的x坐标
        y = u[1] + dy[d]  # 新的y坐标
        
        # 检查新坐标是否在有效范围内，且为镜子
        if x < 0 or x >= n or y < 0 or y >= m or a[x][y] == 0:
            continue  # 跳过不合法的坐标或墙体

        # 更新接收时间
        if dis[x][y] > dis[u[0]][u[1]] + a[u[0]][u[1]]:
            dis[x][y] = dis[u[0]][u[1]] + a[u[0]][u[1]]  # 更新新镜子的接收时间
            heapq.heappush(q, [dis[x][y], x, y])  # 将新镜子加入队列

# 计算所有镜子接收到光芒的最晚时间
ans = 0  # 最晚接收到光芒的时间
ok = True  # 用于判断是否所有镜子都接收到光芒

# 遍历所有镜子，找出接收到光芒的最晚时间
for i in range(n):
    for j in range(m):
        if a[i][j] != 0:  # 只检查镜子
            ans = max(ans, dis[i][j])  # 更新最晚时间

# 输出结果，如果未能接收到光芒，返回-1
print(ans if ans != 10**9 else -1)

Java代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // 创建输入扫描器
        while (in.hasNextInt()) { // 当输入有整数时继续循环
            int n = in.nextInt(); // 读取矩阵的行数
            int m = in.nextInt(); // 读取矩阵的列数
            int[][] mirrors = new int[n][m]; // 创建二维数组存储镜子的等级
            int initI = in.nextInt(); // 读取光源镜子的起始行坐标
            int initJ = in.nextInt(); // 读取光源镜子的起始列坐标
            
            // 输入矩阵数据，填充镜子的等级
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    mirrors[i][j] = in.nextInt(); // 读取每个镜子的等级
                }
            }
            
            // 初始化接收时间数组，设为一个很大的数（模拟无穷大）
            int[][] times = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    times[i][j] = Integer.MAX_VALUE; // 设置为无穷大
                }
            }

            // 使用优先队列来实现Dijkstra算法
            Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[2] - o2[2]; // 根据时间进行比较
                }
            }); // 队列存储[x, y, 耗时]

            int[][] visited = new int[n][m]; // 访问标记数组
            queue.offer(new int[]{initI, initJ, 0}); // 将起始点加入队列

            // Dijkstra算法主循环
            while (!queue.isEmpty()) {
                int[] poll = queue.poll(); // 从队列中取出耗时最小的元素
                int x = poll[0]; // 当前镜子的行坐标
                int y = poll[1]; // 当前镜子的列坐标
                int time = poll[2]; // 当前镜子的接收时间
                
                // 检查坐标是否在有效范围内
                if (x < 0 || x >= mirrors.length || y < 0 || y >= mirrors[0].length) {
                    continue; // 如果超出范围，跳过
                }
                if (mirrors[x][y] == 0) { // 如果是墙体，跳过
                    continue;
                }
                if (visited[x][y] == 1) { // 如果该镜子已访问，跳过
                    continue;
                }
                
                visited[x][y] = 1; // 标记该镜子已访问
                times[x][y] = time; // 记录该镜子接收光芒的时间

                // 将四个方向的邻接镜子加入队列，计算新的接收时间
                queue.offer(new int[]{x - 1, y, time + mirrors[x][y]}); // 上
                queue.offer(new int[]{x + 1, y, time + mirrors[x][y]}); // 下
                queue.offer(new int[]{x, y - 1, time + mirrors[x][y]}); // 左
                queue.offer(new int[]{x, y + 1, time + mirrors[x][y]}); // 右
            }
            
            // 计算所有镜子接收到光芒的最晚时间
            int max = 0; // 存储最晚接收到光芒的时间
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (mirrors[i][j] != 0) { // 只检查镜子
                        max = Math.max(max, times[i][j]); // 更新最晚接收时间
                    }
                }
            }
            // 输出结果，如果未能接收到光芒，则返回-1
            if (max == Integer.MAX_VALUE) {
                System.out.println(-1); // 如果没有镜子接收到光芒，输出-1
            } else {
                System.out.println(max); // 输出所有镜子接收到光芒的最晚时间
            }
        }
    }
}

#P1554. 2023.08.23-秋招-第三题-光芒散射

2023.08.23-秋招-第三题-光芒散射