Rotting Oranges
简单的bfs题, 注意的是判断一下特殊情况, 比如给的数组只有1个fresh orange的情况.
|
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 |
class Solution { public int orangesRotting(int[][] grid) { int[][] dirs = new int[][]{{0,1},{1,0},{-1,0},{0,-1}}; int res = 0; // minutes int count = 0; // count how many fresh Queue<int[]> q = new LinkedList<int[]>(); for(int i = 0 ; i < grid.length; i++) { for(int j = 0 ; j < grid[0].length; j++) { if(grid[i][j] == 2) { q.add(new int[]{i,j}); } else if(grid[i][j] == 1) { count++; } } } if(count == 0) // if no rotten orange return 0; while(!q.isEmpty()) { int size = q.size(); for(int i = 0 ; i < size; i++) { int[] g = q.poll(); for(int[] d : dirs) { if(g[0] + d[0] >= 0 && g[0] + d[0] < grid.length &&g[1] + d[1] >= 0 && g[1] + d[1] < grid[0].length && grid[g[0]+d[0]][g[1]+d[1]] == 1) { grid[g[0]+d[0]][g[1]+d[1]] = 2; q.add(new int[]{g[0]+d[0], g[1]+d[1]}); count--; } } } res++; } if(count != 0) return -1; else return res-1; } } |