蓝桥杯-染色时间

@toc

1、问题描述

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

每个方格有一个染色时间 $t_{ij}$, 不同方格的染色时间可能不同。如果一个方格被触发了染色, 这个方格就会在秒 $t_{ij}$之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。

输入格式

输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。

接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i 行第 j 个整数表示 $t_{ij}$, 即第 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≤ $t_{ij}$≤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，但是队列是先入先出，这道题是根据染色时间大小决定出入顺序，所以我们使用优先级队列实现，我们依次将染色的点加入队列中，每次取出染色耗时最短的点，然后依次将其上下左右四个位置的节点入队，节点的值加上出队的这个节点的染色时间，之后将上下左右这。

对本题来讲，就是 $(1,1)$位置先入队列，然后 $(1,1)$出队，设置其值为0，标记已经被染色，然后向四个方向扩展，由于越界的关系，只能扩展到 $(1,2)$和 $(2,4)$这两个位置，依次将 $(1,2,2+1)$, $(2,1,4+1)$两个节点入队。后面的节点入队和出队类似，这样我们使用优先级队列，每次耗时最短的节点先出队，最后出队的节点就是耗时最久的，他的时间就是最终的输出结果。

关于位置我们定义如下：

public static int[][] dirs={
            {-1,0},//上
            {0,1},//右
            {1,0},//下
            {0,-1}//左
};

3、代码实现

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秒，这已经非常快了。