LeetCode 994.腐烂的橘子

解法一，直接暴力。假设网格两个边长分别为 n 和 m ,复杂度 O(n*m*max(n, m))。

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。

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上解法二用的时间更多，很奇怪。