994. Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Example
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
思路
先遍历一边二维数组，有两个目的
- 统计新鲜橘子数量，到最后如果还有剩余的新鲜橘子，那就说明没有全部腐烂，直接返回-1
- 把已经腐烂的橘子放进队列中，这就是首批腐烂橘子，对应着 res -〉0
接下来就是依次取出队列中腐烂橘子，做广度遍历，只要在边界范围内并且是新鲜橘子的，就将其腐烂，然后也入队列，每一批次队列的橘子取完，那这回合的腐烂就结束了，res++
题解
Integer freshCount = 0;
public int orangesRotting(int[][] grid) {
int res;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1)
freshCount++;
if (grid[i][j] == 2)
queue.add(new int[]{i, j});
}
}
res = bfs(grid, queue);
return freshCount == 0 ? res : -1;
}
public int bfs(int[][] grid, Queue<int[]> queue) {
int res = 0;
int[][] dire = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty() && freshCount != 0) {
int size = queue.size();
for (int j = 0; j < size; j++) {
int[] curPos = queue.poll();
for (int i = 0; i < dire.length; i++) {
int curRow = curPos[0] + dire[i][0];
int curCol = curPos[1] + dire[i][1];
if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid[0].length
|| grid[curRow][curCol] != 1)
continue;
queue.add(new int[]{curRow, curCol});
grid[curRow][curCol] = 2;
freshCount--;
}
}
res++;
}
return res;
}