在给定的网格中,每个单元格可以有以下三个值之一:

值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,任何与腐烂的橘子(在 4
个正方向上)相邻的新鲜橘子都会腐烂。

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

题目链接: https://leetcode-cn.com/problems/rotting-oranges/

破题思路

每一轮,腐烂将会从每一个烂橘子蔓延到与其相邻的新鲜橘子上。一开始,腐烂的橘子拥有深度为 0,每一轮腐烂会从腐烂橘子传染到之相邻新鲜橘子上,并且设置这些新的腐烂橘子的深度为自己深度 +1,我们想知道完成这个过程之后的最大深度值是多少。

算法

我们可以用一个宽度优先遍历来建模这一过程。因为我们总是选择去使用深度值最小的(且之前未使用过的)腐烂橘子去腐化新鲜橘子,如此保证每一个橘子腐烂时的深度标号也是最小的。

我们还应该检查最终状态下,是否还有新鲜橘子。

代码


class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> depth = new HashMap<>();
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
        if (queue.size()==0) return -1;

        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.poll();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }

        for (int[] row : grid)
            for (int v : row)
                if (v == 1)
                    return -1;
        return ans;

    }
}

收获

我觉得这里的思路很棒,第一遍自己写到这里的时候,不知道queue中到底该怎么存储行值和列值,这里有一个code就表现了两个属性,当我们要从code中反推出行和列的时候只需要反过来做一个除法和取余数就ok了

int code = r * C + c;
queue.add(code);
----------------------------
int r = code / C, c = code % C;

标签: leetcode, java

仅有一条评论

  1. get到了力扣这个网站~

添加新评论