1 solutions
-
0
题面描述
塔子哥有一些神奇的镜子,能够吸收光芒并在一定时间后散射。镜子分为一级镜和二级镜,一级镜散射光芒需1毫秒,而二级镜需2毫秒。塔子哥将这些镜子放在一个二维矩阵中,并给定光源镜子的坐标。输入包括矩阵的行列数、光源坐标以及每个位置的镜子等级(0为墙体,1为一级镜,2为二级镜)。输出为所有镜子最早吸收到光芒的时间,若有镜子无法吸收到光芒则输出-1。
思路:Dijkstra
目标是找到所有镜子接收到光芒的最早时间。因此可以想到单源最短路算法:dijkstra
首先,我们需要创建一个二维数组
dis
来存储每个镜子接收到光芒的时间,初始值设为一个较大的数。同时,我们需要一个二维数组bk
来标记每个镜子是否已经接收到光芒,初始值设为False
。然后,我们使用优先队列
q
,并将初始镜子的坐标和接收到光芒的时间(设为 0)加入队列。接下来,我们进行Dijkstra算法。在每一步,我们取出队列中时间最早的镜子,然后更新其四个方向的镜子的接收时间。如果新的接收时间比当前的接收时间早,我们就更新接收时间,并将新的镜子加入队列。
最后,我们遍历所有的镜子,找出接收到光芒的最晚时间,即为所有镜子都能够吸收到光芒的最早时间。
算法步骤:
-
初始化:
- 创建一个二维数组
dist
来存储每个镜子接收到光芒的时间,初始值设为一个较大的数(INT_MAX / 2
),以避免溢出。 - 创建一个二维布尔数组
visited
来标记每个镜子是否已经接收到光芒,初始值设为false
。 - 使用优先队列
pq
存储每个镜子的坐标和接收到光芒的时间,并将初始镜子的坐标和时间(0)加入队列。
- 创建一个二维数组
-
Dijkstra算法:
- 在每一步中,从队列中取出时间最早的镜子,检查其四个方向(上下左右)的邻接镜子。
- 如果邻接镜子的接收时间比当前的接收时间早,则更新接收时间,并将邻接镜子加入队列。
- 继续这个过程,直到所有可达的镜子都接收到光芒或队列为空。
-
结果计算:
- 遍历所有镜子,找出接收到光芒的最晚时间,即为所有镜子都能够吸收到光芒的最早时间。如果有镜子仍未接收到光芒,则返回-1。
时间复杂度
代码
C++
python代码
Java代码
-
- 1
Information
- ID
- 47
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 66
- Accepted
- 12
- Uploaded By