解法一,直接暴力。假设网格两个边长分别为 n
和 m
,复杂度 O(n*m*max(n, m))
。
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 class Solution { public int orangesRotting (int [][] grid) { int n = grid.length, m = grid[0 ].length; int cnt = 0 , ans = 0 ; int vis[][] = new int [n][m]; while (true ) { int cur = 0 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (grid[i][j] == 1 ) cur++; } } if (cnt == 0 ) ans = cur; else { if (ans == cur) return -1 ; else ans = cur; } if (ans == 0 ) return cnt; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (grid[i][j] == 2 && vis[i][j] == cnt) { if (i - 1 >= 0 && grid[i - 1 ][j] == 1 ) { grid[i - 1 ][j] = 2 ; vis[i - 1 ][j] = cnt + 1 ; } if (j - 1 >= 0 && grid[i][j - 1 ] == 1 ) { grid[i][j - 1 ] = 2 ; vis[i][j - 1 ] = cnt + 1 ; } if (i + 1 < n && grid[i + 1 ][j] == 1 ) { grid[i + 1 ][j] = 2 ; vis[i + 1 ][j] = cnt + 1 ; } if (j + 1 < m && grid[i][j + 1 ] == 1 ) { grid[i][j + 1 ] = 2 ; vis[i][j + 1 ] = cnt + 1 ; } } } } cnt++; } } }
解法二,广度优先搜索。
先找出腐烂的橘子,添加进 queue
中。
队列 queue
只让腐烂的橘子入队;
出队时,让当前腐烂橘子四周的新鲜橘子都变为腐烂,即 grid[newX][newY] = 2
。
用 minute
记录腐烂的持续时间,每一层的橘子在内一层的橘子的腐烂时间基础之上自增 1
,代表时间过了 1
分钟。
最后检查网格中是否还有新鲜的橘子:
有,返回 -1
代表 impossible
。
没有则返回 minute
。
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 class Pos { int x, y, minute; public Pos (int _x, int _y, int _minute) { x = _x; y = _y; minute = _minute; } } class Solution { static int [][] dir = {{0 , 1 }, {0 , -1 }, {-1 , 0 }, {1 , 0 }}; public int orangesRotting (int [][] grid) { Queue<Pos> queue = new LinkedList<>(); int n = grid.length, m = grid[0 ].length; int minute = 0 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (grid[i][j] == 2 ) { queue.add(new Pos(i, j, minute)); } } } while (!queue.isEmpty()) { Pos cur = queue.poll(); minute = cur.minute; for (int i = 0 ; i < 4 ; i++) { int newX = cur.x + dir[i][0 ]; int newY = cur.y + dir[i][1 ]; if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1 ) { queue.add(new Pos(newX, newY, minute + 1 )); grid[newX][newY] = 2 ; } } } for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (grid[i][j] == 1 ) return -1 ; } } return minute; } }
理论上讲解法二应该比解法一速度快,但是在leetcode
上解法二用的时间更多,很奇怪。