一、题目

描述

给定一个 𝑛×𝑚 n×m  的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围： 1≤𝑛,𝑚≤1000 1≤n,m≤1000  ，网格中的值满足 0≤𝑣𝑎𝑙≤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

二、思路解析

这道题用到的是 bfs（宽度优先遍历）算法，对于该算法的具体实现及细节，本篇博客不会过多阐述。

首先，我们需要定义一个二维数组 vis 来记录每个格子，在每一轮的遍历中是否被访问过。

然后遍历整个网格，将所有腐烂的苹果的坐标加入到队列中，并将它们标记为已访问。

开始 BFS，我们就从队列中依次取出腐烂的苹果，向上下左右四个方向传播病菌，并标记相邻的完好苹果为已访问，同时将它们加入队列。

每次完成一轮传播后，时间加一。

最后，我们检查网格中是否还有完好的苹果未被腐烂，如果有则返回 -1，否则返回传播的时间。

具体实现请看下面代码👇

三、完整代码

import java.util.*;public class Solution {int m, n;int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public int rotApple (ArrayList<ArrayList<Integer>> grid) {m = grid.size();n = grid.get(0).size();boolean[][] vis = new boolean[m][n];Queue<int[]> q = new LinkedList<>();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 ret = 0;while(!q.isEmpty()){int sz = q.size();while(sz-- != 0){int[] t = q.poll();int a = t[0];int b = t[1];for(int i = 0; i < 4; i++){int x = a + dx[i];int y = b + 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});}}}ret++;}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 ret - 1;}
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！