详解腐烂的苹果(图+代码+广度优先遍历)

描述

给定一个 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 

示例1

输入：

[[2,1,1],[1,0,1],[1,1,1]]

复制返回值：

4

复制

示例2

输入：

[[2,1,0],[1,0,1],[0,0,0]]

复制返回值：

-1

思路

第一步我们先要明白,每个腐烂的苹果都会同时开始向周围腐烂

第二步,我们把所有坏的苹果放进栈,同时出栈,开始腐烂 ,也就是广度优先遍历

 第三步,我们开始记录被腐烂的苹果,即可,切记我们要把被腐烂的苹果也就是新腐烂的苹果放进栈,这里你可能想为啥不把旧腐烂苹果重新放进栈去呢?那我反问你,旧腐烂的苹果周边都被腐烂了,还用重新扩散取腐烂吗

 

代码

import java.util.*;public class Solution {int []dx = {0, 0, 1, -1};int [] dy = {1, -1, 0, 0};boolean [][]vis;//标记腐烂的苹果public int rotApple (ArrayList<ArrayList<Integer>> list) {int m = list.size(), n = list.get(0).size();vis = new boolean[m][n];int count = 0;//把腐烂的苹果放进栈Queue<int []>q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (list.get(i).get(j) == 2)q.add(new int[] {i, j});}}//因为每个腐烂的苹果都是同时开始传染,所以同时出栈广度优先遍历while (!q.isEmpty()) {int sz = q.size();while (sz-- != 0) {int []t=q.poll();int a = t[0], b = t[1];for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&list.get(x).get(y) == 1) {//找到一个好苹果开始腐烂vis[x][y] = true;q.add(new int [] {x, y});}}}count++;}//判断是否有永远不会腐烂的苹果for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (vis[i][j] == false&&list.get(i).get(j)==1)return -1;}}return count-1;}
}