????????臨時抱抱佛腳，太浮躁了，藍橋杯已經快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;}
}
)
)
