临时抱抱佛脚，太浮躁了，蓝桥杯已经快1个半月没做题了。
本人比较菜，感觉这个时间节点也只能把暴力题给尽量多做做，找找做题手感，其他就纯凭运气了吧。T-T。
题目
问题描述
小蓝有一个 n 行 m 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。
每个方格有一个染色时间 tij, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 tij秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。
给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。
输入格式
输入的第一行包含两个整数 n,m，分别表示棋盘的行数和列数。
接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每个方格的染色时间。该部分的第 i 行第 j 个整数表示 tij, 即第 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≤tij≤1000。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
题意
就是他有一个n*m的棋盘，然后每个方格都可以被染色，但是只有到了那个染色时间，这个方格才能触发染色。从他刚被触发，到染色完成变成彩色，需要tij的时间。让你求，n*m个格子全都染色完成时的时间是多少。
思路
这题会很容易想到是BFS，就是从最先变成彩色的点开始向外扩展，每次更新时间就可以。我们先来看一下代码。
代码主要用到优先队列，因为我们需要让染色时间最短的先出队列。
这里是菜鸟踩坑的地方（踩的第一个坑）：
但是我最开始并没有用优先队列，我是直接先对list按照tij从小到大排序，然后在bfs里用的普通队列，我自认为bfs()中的普通队列也是按照tij从小到大排好的。不知道你们有没有这种想法。这种想法是肯定不可以的啊。原因如下，因为按下面这份代码来说，如果你直接在main方法里将list按照tij排序，你只能保证第一个进入普通队列的tij值一定是最小的，但是后续的你无法保证。
为什么呢？
因为当你第一次进入while的时候，肯定tij最小的那个已经进入队列了，然后你就要开始四个方向的遍历，但是你无法保证(tx,ty)上的tij一定是第二小的，对吧。而且我们上下左右定义的顺序都不一样，更何况说一定能保证tij从小到大进队列。所以普通队列不可行，必须在bfs()里用优先队列，让每一次出队的都是队列中tij最小的。
这里是菜鸟难以跨越的第二个坑T/\T：
就是题目既然问你最终n*m个格子染色完成的时间了，所以bfs()中肯定要有一个变量记录一下这个结果吧，那么怎么记录呢？本菜鸟就卡这了。
最开始我写的代码特离谱，static里定义了一个ans，bfs()里定义了res，又是比较大小啥的。。。
其实就在bfs()里用一个变量持续更新就行了，下面代码里用的是res。下面讲一下更新res的逻辑：while外我定义res的初始值为0，当第一次进入while循环时，直接让res = poll[2]即可。就该题而言，第一次进入while时，res = poll[2] = 1。为什么让res=poll[2]，而不是用max去取res和poll[2]的最大值，我们后面会说。
之后我们进行四个方向的尝试，如果更新后的格子坐标不越界并且未被访问过，我们就将其坐标以及更新后的tij加到队列中，并将vis设为true。
为什么要在这个地方更新tij？？？
先看下边的图，辅助我们理解。
上边的(0,1,3)入队啥的，(0,1)是格子索引，3是更新完的时间。
还是这个问题：为什么要在这个地方更新tij？？？
就是不知道能不能get到这个点，就是你在queue.offer里更新时间的话，是有一个向后性的，也就是说你更新的永远是最新的节点，相当于你在直接的更新结果，即你求的是从起点到终点的累计时间。
就是不知道有没有人会这么写，可能会有点误导，这就是本菜鸟踩的第三个大坑：
不在queue.offer里更新时间，直接queue.offer(tx,ty,g[tx][ty]);然后把前边的res = poll[2];改成res += poll[2];这样肯定是不对的啊。如果你这样写的话，那res岂不是表示所有出队节点时间的总和了吗，因为直接queue.offer(tx,ty,g[tx][ty]);，所以并没有更改每个格子的时间。
下面来说一下为什么让res=poll[2]，而不是用max去取res和poll[2]的最大值？？？
这个问题也困了我很久，但是你看右上方图片里写的文字表述，应该可以发现，收到优先队列的影响，每次出来的都是tij最短的，所以受他影响的格子的完成染色的时间一定是最早的。为什么？因为你一把他触发，vis在代码里就设为true了，后边出队的格子没法影响它已经影响过的格子了。所以每次的poll[2]其实就是当前格子被染色完成的最早的时间点。
希望能帮助到大家。虽然文章还有很多不足之处。
代码
import java.util.*;
public class 染色时间 {static int n;static int m;static int[][]g;static boolean [][]vis;static int [][]f = {{1,0},{-1,0},{0,1},{0,-1}};static List<int []> list;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();g = new int[n][m];list = new ArrayList<>();vis = new boolean[n][m];for(int i = 0;i < n;i ++) {for (int j = 0;j < m;j ++) {g[i][j] = sc.nextInt();list.add(new int[]{i,j,g[i][j]});}}int ans = bfs(list.get(0)[0],list.get(0)[1],list.get(0)[2]);System.out.println(ans);}public static int bfs(int x, int y, int time) {PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->a[2]-b[2]);queue.offer(new int[]{x,y,time});vis[x][y] = true;int res = 0;while (!queue.isEmpty()) {int []poll = queue.poll();res = poll[2];for(int i = 0;i < 4;i ++) {int tx = poll[0] + f[i][0];int ty = poll[1] + f[i][1];if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty]) {queue.offer(new int[]{tx,ty,g[tx][ty] + res});vis[tx][ty] = true;}}}return res;}
}
)
)
