【重点】【BFS】994.腐烂的橘子

题目

法1：BFS

此方法类似二叉树层次搜索。

class Solution {
    public int orangesRotting(int[][] grid) {
        int[] dx = {-1, 1, 0, 0}; // 方向数组
        int[] dy = {0, 0, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length, n = grid[0].length, res = 0, flash = 0;
        int[][] copyGrid = new int[m][n]; // 复制，保证不改变原始输入数组
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                copyGrid[i][j] = grid[i][j];
                if (grid[i][j] == 1) {
                    ++flash;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        
        while (flash > 0 && !queue.isEmpty()) {
            ++res;
            int tmpSize = queue.size();
            for (int i = 0; i < tmpSize; ++i) {
                int[] loc = queue.poll();
                int x = loc[0], y = loc[1];
                for (int k = 0; k < 4; ++k) {
                    int newX = x + dx[k];
                    int newY = y + dy[k];
                    if ((newX >= 0 && newX < m) 
                            && (newY >= 0 && newY < n)
                            && copyGrid[newX][newY] == 1) {
                        copyGrid[newX][newY] = 2;
                        queue.offer(new int[]{newX, newY});
                        --flash;
                    }
                }
            }
        }

        if (flash > 0) {
            return -1;
        } 

        return res;
    }
}