题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

题目分析

腐烂是按时间蔓延的，因此使用BFS进行模拟即可。
记录每一层次的个数，该层全部出队时，时间 + 1。
最后检查一下是否还有新鲜橘子。

Java

private int[][] direction = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int orangesRotting(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;

    // 存储腐烂橘子
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            }
        }
    }

    // 模拟时间流逝
    int time = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size-- > 0) {
            int[] node = queue.poll();
            int i = node[0], j = node[1];
            for (int index = 0; index < direction.length; index++) {
                int[] dir = direction[index];
                int nextI = i + dir[0];
                int nextJ = j + dir[1];
                if (isValid(nextI, nextJ, m, n) && grid[nextI][nextJ] == 1) {
                    queue.offer(new int[]{nextI, nextJ});
                    grid[nextI][nextJ] = 2;
                }
            }
        }
        time++;
    }

    // 检查是否有新鲜橘子
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                return -1;
            }
        }
    }
    return Math.max(0, time - 1);
}

private boolean isValid(int i, int j, int m, int n) {
    return i >= 0 && i < m && j >= 0 && j < n;
}

Kotlin

private val direction = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

fun orangesRotting(grid: Array<IntArray>): Int {
    val queue = LinkedList<IntArray>()
    for (i in grid.indices) {
        for (j in grid[0].indices) {
            if (grid[i][j] == 2) {
                queue.offer(intArrayOf(i, j))
            }
        }
    }

    var time = 0
    while (!queue.isEmpty()) {
        var size = queue.size
        while (size-- > 0) {
            val node = queue.poll()
            val i = node[0]
            val j = node[1]
            for (dir in direction) {
                val nextI = i + dir[0]
                val nextJ = j + dir[1]
                if (nextI in grid.indices && nextJ in grid[0].indices && grid[nextI][nextJ] == 1) {
                    queue.offer(intArrayOf(nextI, nextJ))
                    grid[nextI][nextJ] = 2
                }
            }
        }
        time++
    }

    for (i in grid.indices) {
        for (j in grid[0].indices) {
            if (grid[i][j] == 1) {
                return -1
            }
        }
    }

    return max(0, time - 1)
}