广度优先搜索
这个方法是之前在leetcode另一个bfs学到的,很有用,算是一个小小扩展。
class Solution {
public int orangesRotting(int[][] grid) {
Queue<int[]> queue = new LinkedList<>();
int dx[] = new int[]{1, 0, -1, 0};
int dy[] = new int[]{0, 1, 0, -1};
int cnt = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) {
queue.add(new int[]{i, j});
}
if (grid[i][j] == 1) {
cnt++;
}
}
}
int ans = 0;
while (!queue.isEmpty() && cnt > 0) {
int size = queue.size();
if (size > 0) {
ans++;
}
for (int i = 0; i < size; i++) {
int arr[] = queue.poll();
for (int j = 0; j < 4; j++) {
int x = arr[0] + dx[j];
int y = arr[1] + dy[j];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
grid[x][y] = 2;
cnt--;
queue.add(new int[]{x, y});
}
}
}
}
return cnt > 0 ? -1 : ans;
}
}