【Hot100】LeetCode—994. 腐烂的橘子

---

• 题目连接：994. 腐烂的橘子

1- 思路

BFS+Queue队列

思路：先 ①遍历存储腐烂橘子的下标、②

• ① 队列的作用：Queue<int[]> queue = new LinkedList<>()存储腐烂橘子的坐标
• ② BFS思路
  • 根据队列非空，和 cur > 0 的时候
  • 遍历 Queue ： 中的坐标，实现BFS 四个方向的腐烂

---

2- 实现

⭐994. 腐烂的橘子——题解思路

class Solution {public int orangesRotting(int[][] grid) {// 1. 数据结构int round = 0;int fresh = 0;Queue<int[]> queue = new LinkedList<>();int row = grid.length;int col = grid[0].length;// 2. 遍历收集 queue的结果for(int i = 0 ; i < row;i++){for(int j = 0 ; j < col ;j++){if(grid[i][j] == 1){fresh++;}if(grid[i][j] == 2){queue.add(new int[]{i,j});}}}int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};while(!queue.isEmpty() && fresh>0){int n = queue.size();for(int j = 0; j < n ;j++){int[] cur = queue.poll();int nowX = cur[0];int nowY = cur[1];for(int z = 0 ; z < 4 ;z++){int newX = nowX + directions[z][0];int newY = nowY + directions[z][1];if(newX>=0 && newX< row && newY>=0 && newY<col && grid[newX][newY] ==1 ){grid[newX][newY] = 2;queue.offer(new int[]{newX,newY});fresh--;}}}round++;}if(fresh==0) return round;return -1;}
}

---

3- ACM 实现

public class rotOrange {public static int orange(int[][] grid){// 数据结构int row = grid.length;int col = grid[0].length;Queue<int[]> queue = new LinkedList<>();int round = 0;int fresh = 0;// 遍历记录腐烂橘子坐标for(int i = 0 ; i < row;i++){for(int j = 0 ; j < col;j++){if(grid[i][j] == 1){fresh++;}if(grid[i][j] == 2){queue.add(new int[]{i,j});}}}int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};// 遍历腐烂的橘子while(!queue.isEmpty() && fresh>0){// 定义 n 遍历int n = queue.size();for(int i = 0 ; i < n;i++){int[] now = queue.poll();int nowX = now[0];int nowY = now[1];for(int j = 0 ; j <4;j++){int newX = nowX + dir[j][0];int newY = nowY + dir[j][1];if(newX>=0 && newX< row && newY>=0 && newY<col && grid[newX][newY] == 1){grid[newX][newY] = 2;queue.offer(new int[]{newX,newY});fresh--;}}}round++;}if(fresh==0) return round;return -1;}public static void main(String[] args) {// 处理输入Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.substring(2,input.length()-2);String[] rows = input.split("\\],\\[");int m = rows.length;int n = rows[0].split(",").length;int[][] grid = new int[m][n];for(int i = 0 ; i < m;i++){String[] row = rows[i].split(",");for(int j = 0 ; j < n ;j++){grid[i][j] = Integer.parseInt(row[j]);}}System.out.println("结果是"+orange(grid));}
}