蓝桥杯-染色时间(优先级队列)

时间:2022-07-05 01:03:39


蓝桥杯-染色时间

  • 1、问题描述
  • 2、解题思路
  • 3、代码实现(AC)

1、问题描述

  小蓝有一个 nm 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

蓝桥杯-染色时间(优先级队列), 不同方格的染色时间可能不同。如果一个方格被触发了染色, 这个方格就会在秒蓝桥杯-染色时间(优先级队列)之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

  给定每个方格的染色时间, 在时刻 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;
    }
}

蓝桥杯-染色时间(优先级队列)

  我试了下,使用StreamTokenizerScanner大概快了400ms左右,别小瞧这几百毫秒,因为这道题最大运行时间也就1秒,这已经非常快了。