腐爛的蘋果

給定一個?n×m?n×m??的網格，其中每個單元格中可能有三種值中的一個 0 , 1 , 2。

其中 0 表示這個格子為空、1 表示這個格子有一個完好的蘋果，2 表示這個格子有一個腐爛的蘋果。

腐爛的蘋果每分鐘會向上下左右四個方向的蘋果傳播一次病菌，并導致相鄰的蘋果腐爛。請問經過多少分鐘，網格中不存在完好的蘋果。如果有蘋果永遠不會腐爛則返回 -1

數據范圍：?1≤n,m≤1000?1≤n,m≤1000??，網格中的值滿足?0≤val≤2?0≤val≤2?

經典廣度優先遍歷題：

這里介紹使用到的元素：

boolean vis[][]?用于記錄好的蘋果是否被感染

偏移數組

隊列，因為需要同時感染，用于同時向四周感染并記錄接收感染后的蘋果（用于后續感染）

int time 用于記錄感染消耗的時間

題解：

1.統計腐爛蘋果進入隊列

2.每分鐘腐爛蘋果都會向四周擴散，將隊列中的腐爛蘋果彈出，并向四周擴散，使用vis記錄被感染的蘋果，并把被傳染的蘋果再次加入隊列。

3.如果隊列中還有元素就繼續執行，并使時間加1

4.結合vis[]統計是否還有好的蘋果。有的話就輸出-1，否則輸出time

代碼：

import java.util.*;public class Solution {int m, n;int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};boolean[][] vis;public int rotApple (ArrayList<ArrayList<Integer>> grid) {// write code herem = grid.size();n = grid.get(0).size();vis = new boolean[m][n];//標記蘋果是否被感染Queue<int[]> q = new LinkedList<int[]>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid.get(i).get(j) == 2) {q.add(new int[] {i, j});}}}int time = 0;//感染的時間while(!q.isEmpty()) {int len = q.size();while(len-- != 0) {int[] tmp = q.poll();for(int i = 0; i < 4; i++) {int x = tmp[0] + dx[i];int y = tmp[1] + dy[i];if(x >= 0 && x < m && y >= 0 && y < n &&!vis[x][y] && grid.get(x).get(y) == 1) {vis[x][y] = true;//標記為已感染q.add(new int[] {x, y});//用于繼續向后感染}}}time++;}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid.get(i).get(j) == 1 && !vis[i][j]) {return -1;}}}return time-1;//因為最后一個好蘋果再向周圍感染一定感染不到}
}