题目

法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;}
}