994. 腐烂的橘子 - 力扣(LeetCode)
使用bfs,先遍历所有的橘子,统计所有的橘子数量,然后把腐烂的橘子放入队列当中,然后进行bfs遍历,套用bfs的模版,但是每一次出队的橘子(腐烂的橘子)需要统计一下数量,用来bfs结束之后比对是否感腐烂完全。每一层广搜遍历需要把时间加一。
bfs结束后,如果出队的橘子小于统计所有的橘子,说明没有腐烂完全,返回-1 ,如果统计的橘子数量为0,返回0,因为没有橘子腐烂,否则返回统计的时间
import java.util.LinkedList;
import java.util.List;public class Q994 {static int[] dx = {0, 0, -1, 1};static int[] dy = {-1, 1, 0, 0};public static void main(String[] args) {int[][] grid = new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};int[][] grid ={{0}};int count = 0;//统计总共的橘子,用来判断bfs结束后是否还有橘子int time = -1;int bad = 0;List<int[]> list = new LinkedList<>();for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] != 0) count++;if (grid[i][j] == 2) {list.add(new int[]{i, j});}}}//开始bfswhile (!list.isEmpty()) {int len = list.size();for (int i = 0; i < len; i++) {int[] remove = list.remove(0);bad++;int x = remove[0];int y = remove[1];for (int j = 0; j < 4; j++) {int xx = x + dx[j];int yy = y + dy[j];if (xx >= 0 && xx < grid.length && yy >= 0 && yy < grid[0].length) {if (grid[xx][yy] == 1) {list.add(new int[]{xx, yy});grid[xx][yy] = 2;}}}}time++;}if(count == 0) System.out.println(0);else if(bad<count) System.out.println(-1);else System.out.println(time);;}}