问题
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.
由于腐烂的橘子每次都只能影响周围的橘子,因此采用BFS。
将所有腐烂的橘子加入队列。
如果没有新鲜的橘子,则返回0。
每次出队列,如果周围有新鲜的橘子存在,则将新鲜的橘子替换为腐烂并加入队列。
每个level结束后,time+1。
最后遍历一遍,如果还有新鲜的橘子,返回-1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| class Solution { public int orangesRotting(int[][] grid) { Queue<Integer> q = new LinkedList(); int row = grid.length; int col = grid[0].length; int fresh = 0; for (int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if ( grid[i][j] == 2){ q.add(i * col + j); } else if (grid[i][j] == 1){ fresh++; } } } if(fresh == 0){return 0;} int count = q.size()-1; int temp = 0; int time = -1; while(!q.isEmpty()){ int i = q.peek() / col; int j = q.poll() % col; if(i-1>=0 && grid[i-1][j] == 1){ grid[i-1][j] = 2; q.add((i-1)*col+j); temp++; } if(j-1>=0 && grid[i][j-1] == 1){ grid[i][j-1] = 2; q.add(i*col+(j-1)); temp++; } if(i+1<row && grid[i+1][j] == 1){ grid[i+1][j] = 2; q.add((i+1)*col+j); temp++; } if(j+1<col && grid[i][j+1] == 1){ grid[i][j+1] = 2; q.add(i*col+(j+1)); temp++; } if(count == 0){ count = temp; temp = 0; time++; } count--; } for (int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if ( grid[i][j] == 1){ return -1; } } } return time; } }
|