蓝桥杯-染色时间(优先级队列)
蓝桥杯-染色时间
1、问题描述
小蓝有一个 n 行 m 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。
每个方格有一个染色时间
, 不同方格的染色时间可能不同。如果一个方格被触发了染色, 这个方格就会在秒
之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。
给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。
输入格式
输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。
接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i 行第 j 个整数表示
, 即第 i 行第 j 列的方 格的染色时间。
输出格式
输出一行包含一个整数, 表示整个棋盘完成染色的时间。
样例输入
2 3
1 2 3
4 5 6样例输出
12评测用例规模与约定
对于 30 的评测用例, 1≤n,m≤10 。
对于 60 的评测用例,1≤n,m≤50 。
对于所有评测用例, 1≤n,m≤500,1≤
≤1000 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
2、解题思路
针对输入案例
1 2 3
4 5 6 这里我们假设下标从1开始，对于题中给的输入案例来说，从(1,1)位置开始染色，它的上下左右四个方向所使用的染色时间为：自身染色时间+(1,1)处的染色时间
(1,1)位置处染色后的分布情况如下:
0 3 3
4 5 6 由于题中输入案例(1,2)处比(2,1)处的染色时间快，所以当(1,2)处染色完成之后的分布情况如下:
0 0 6
4 8 6所以，我们其实每次都取得是染色时间最小的，然后再更新它周围没有被染色的节点的染色时间。
有点类似于BFS，但是队列是先入先出，这道题是根据染色时间大小决定出入顺序，所以我们使用优先级队列实现，我们依次将染色的点加入队列中，每次取出染色耗时最短的点，然后依次将其上下左右四个位置的节点入队，节点的值加上出队的这个节点的染色时间，之后将上下左右这。
对本题来讲，就是
位置先入队列，然后
出队，设置其值为0，标记已经被染色，然后向四个方向扩展，由于越界的关系，只能扩展到
和
这两个位置，依次将
,
两个节点入队。后面的节点入队和出队类似，这样我们使用优先级队列，每次耗时最短的节点先出队，最后出队的节点就是耗时最久的，他的时间就是最终的输出结果。
关于位置我们定义如下：
public static int[][] dirs={
{-1,0},//上
{0,1},//右
{1,0},//下
{0,-1}//左
};3、代码实现(AC)
package LanQiaoBei.染色时间;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static int[][] dirs={
{-1,0},
{0,1},
{1,0},
{0,-1}
};
public static void main(String[] args) {
long start = System.currentTimeMillis();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=m ; j++) {
a[i][j]=scan.nextInt();
}
}
//使用优先级队列，每次耗时最短的节点先出队，最后出队的就是耗时最久的。
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(1,1,a[1][1]));//初始将第一个节点入队
a[1][1]=0; //代表这个位置已经染色过了
int count=0;
while(!queue.isEmpty()){ //当队列不为空时
Node node = queue.poll(); //队首元素出队
//将node四个方向的节点入队，并修改为0，标记自己已经染色
for (int[] dir : dirs) {
int x = node.x + dir[0];
int y = node.y + dir[1];
if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!=0){
queue.offer(new Node(x,y,a[x][y]+node.time));
//标记这个位置已经被访问过了
a[x][y]=0;
}
}
//该位置已经染色
a[node.x][node.y]=0;
count=node.time;
}
System.out.println(count);
long end = System.currentTimeMillis();
System.out.println(end-start);
}
}
class Node implements Comparable<Node> {
int x;
int y;
int time;//耗时
public Node(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
@Override
public int compareTo(Node o) {
return this.time-o.time;
}
}上面的代码没问题，但是用
Scanner读取数据会超时，竞赛中一般都要用Java快读使用Java快读的改进代码如下：
package LanQiaoBei.染色时间;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.PriorityQueue;
public class Main1 {
public static int[][] dirs={
{-1,0},//上
{0,1},//右
{1,0},//下
{0,-1}//左
};
public static void main(String[] args) throws IOException {
//使用java快读
StreamTokenizer scan = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
scan.nextToken();
int n = (int) scan.nval;
scan.nextToken();
int m = (int) scan.nval;
int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=m ; j++) {
scan.nextToken();
a[i][j]=(int)scan.nval;
}
}
//使用优先级队列，每次耗时最短的节点先出队，最后出队的就是耗时最久的。
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(1,1,a[1][1]));//初始将第一个节点入队
a[1][1]=0; //代表这个位置已经染色过了
int count=0;
while(!queue.isEmpty()){ //当队列不为空时
Node node = queue.poll(); //队首元素出队
//将node四个方向的节点入队，并修改为0，标记自己已经染色
for (int[] dir : dirs) {
int x = node.x + dir[0];
int y = node.y + dir[1];
if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!=0){
queue.offer(new Node(x,y,a[x][y]+node.time));
//标记这个位置已经被访问过了
a[x][y]=0;
}
}
//该位置已经染色
a[node.x][node.y]=0;
count=node.time;
}
System.out.println(count);
}
}
class Node implements Comparable<Node> {
int x;
int y;
int time;//耗时
public Node(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
@Override
public int compareTo(Node o) {
return this.time-o.time;
}
}
我试了下，使用
StreamTokenizer比Scanner大概快了400ms左右，别小瞧这几百毫秒，因为这道题最大运行时间也就1秒，这已经非常快了。