Leecode第九天,广度优先搜索之矩阵,腐烂的橘子

Leecode第九天,广度优先搜索之矩阵,腐烂的橘子,第1张

Leecode第九天,广度优先搜索之矩阵,腐烂的橘子

第九天,两个广度优先搜索的算法题,先来看第一个

 乍一看没有头绪,那我们先简化一下题目,假如只有一个0,那问题是不是很简单,以唯一的0作为中心做广度优先搜索,设个变量depth,每搜索一层,depth+1。简单解决。

那么现在有多个0,好了,有点复杂,但是换一下思维,把多个0看成“超级0”辐射而来的就轻松解决了,现在题目变成这样:有一个超级0,其他都是1,算出每个1到超级0的距离。但是超级0做广度优先搜索的第一层辐射创造出了多个0,逻辑关系不需要写,现在需要笔者继续完成剩下的广度优先搜索。好的,太简单了,将多个0放进队列,继续做广度优先搜索不OK了吗?看代码

class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int[][] updateMatrix(int[][] matrix) {
        //新建大小一样的矩阵
        int m = matrix.length, n = matrix[0].length;
        int[][] dist = new int[m][n];
        //新建boolean类型数组标记 节点是否访问过
        boolean[][] seen = new boolean[m][n];
        //新建队列放入节点
        Queue queue = new linkedList();
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true;
                }
            }
        }
        // 广度优先搜索
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.offer(new int[]{ni, nj});
                    seen[ni][nj] = true;
                }
            }
        }

        return dist;
    }
}

第二题 腐烂的橘子

刚开始看到这题目,觉得和第一题很相似,只不过最后多个判断有没有全部腐烂而已,见代码

class Solution {
    int[] dx = new int[]{1,0,0,-1};
    int[] dy = new int[]{0,1,-1,0};
    
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int time = 0;
        //找到所有腐烂的橘子加入队列中, 并统计新鲜水果数量
        int normalCount = 0;
        Queue queue = new linkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
               if (grid[i][j] == 2){
                   queue.add(new int[]{i, j});
               } else if(grid[i][j] == 1){
                   normalCount++;
               }
            }
        }
        //没有烂橘子
        if (normalCount == 0){
            return 0;
        }
        //猎杀时刻
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                int row = point[0];
                int column = point[1];
                for (int j = 0; j < dx.length; j++) {
                    int x = row + dx[j];
                    int y = column + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){
                        //好橘子烂掉
                        grid[x][y] = 2;
                        normalCount--;
                        queue.add(new int[]{x,y});
                    }
                }
            }
            time++;
        }
        return normalCount == 0 ? time -1 : -1;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5594713.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存