leetcode广度优先搜索（bfs）

柔光的暖阳◎ 2022-09-04 12:41 201阅读 0赞

1.  01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。  
输入：mat = \[\[0,0,0\],\[0,1,0\],\[1,1,1\]\]  
输出：\[\[0,0,0\],\[0,1,0\],\[1,2,1\]\]

此类为图中多起点的搜索问题，将多个起点看作一个整体，先寻找图中所有的0作为起点，其他格子设置为-1，表示还未访问过的格子。  
采用队列存储，先把所有的0入队，之后依次出队，并把出队的0能够到达的格子入队。  
当前所有为0能够到达的格子，则这些格子值为1（到达最近的0的距离），等到所有的0出队完成；第二批格子同样执行操作，他们能够到达的第三批格子的值为之前的+1.

class Solution {
        
        public int[][] updateMatrix(int[][] mat) {
        
        Queue<int[]> queue=new LinkedList<>();
        int m=mat.length;int n=mat[0].length;
        for(int i=0;i<m;i++){
        
            for(int j=0;j<n;j++){
        
                if(mat[i][j]==0){
        
                    queue.offer(new int[] {
        i,j});
                }
                else
                {
        
                    mat[i][j]=-1;
                }
            }
        }
        int[] dx=new int[]{
        -1,1,0,0};
        int[] dy=new int[]{
        0,0,1,-1};
        while(!queue.isEmpty()){
        
            int[] point=queue.poll();
            int x=point[0];int y=point[1];
            for(int i=0;i<4;i++){
        
            int newx=x+dx[i];int newy=y+dy[i];
            if(newx<m&&newx>=0&&newy<n&&newy>=0&&mat[newx][newy]==-1){
        
                mat[newx][newy]=mat[x][y]+1;
                queue.offer(new int[]{
        newx,newy});
            }
            }
        }
        return mat;
        }
    }

1.  腐烂的橘子

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

值 0 代表空单元格；
    值 1 代表新鲜橘子；
    值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

输入：\[\[2,1,1\],\[1,1,0\],\[0,1,1\]\]  
输出：4

与上题类似，同样从烂橘子出发，找到新鲜橘子，更改之后入队。不同的地方有，需要统计新鲜橘子的个数，腐烂过程的结束条件除了队列为空，还有新鲜橘子的个数归零，对应\[1,0\]这种情况，只需一次就可，但第一次执行完成后队列并不为空。  
本题的计算时间变量，每当执行队列长度的次数后加一。例如初始3个腐烂的橘子，执行3次后，时间加一，当前队列中的个数为这三个橘子感染的数量，对应第二轮。

class Solution {
        
        public int orangesRotting(int[][] matrix) {
        
            Queue<int[]> queue = new LinkedList<>();
            int m = matrix.length, n = matrix[0].length;
            int cnt1=0;
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (matrix[i][j] == 2) {
        
                        queue.offer(new int[] {
        i, j});
                    }
                    else if(matrix[i][j]==1){
        
                        cnt1++;
                    }
                }
            }
            int[] dx = new int[] {
        -1, 1, 0, 0};
            int[] dy = new int[] {
        0, 0, -1, 1};
            int count=0;
            while (!queue.isEmpty()&&cnt1>0) {
        
                count++;
                int size=queue.size();
                for(int q1=0;q1<size;q1++){
        
                int[] point = queue.poll();
                int x = point[0], y = point[1];
                for (int i = 0; i < 4; i++) {
        
                    int newX = x + dx[i];
                    int newY = y + dy[i];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n 
                            && matrix[newX][newY] == 1) {
        
                        matrix[newX][newY] = 2;
                        cnt1--;
                        queue.offer(new int[] {
        newX, newY});
        
                    }
                }
            }//一轮感染完成
            }
            int flag=1;//看是否有没感染的
            for(int i=0;i<m;i++){
        
                for(int j=0;j<n;j++){
        
                    if(matrix[i][j]==1)count=-1;
                }
            }
            return count;
    
        }
    }

1.  省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected\[i\]\[j\] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected\[i\]\[j\] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。  
isConnected = \[\[1,1,0\],\[1,1,0\],\[0,0,1\]\]  
2

class Solution {
        
        public int findCircleNum(int[][] isConnected) {
        
        int l=isConnected.length;
        int circle=0;
        boolean visited[]=new boolean[l];
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<l;i++){
        
            if(!visited[i]){
        
                queue.offer(i);
                while(!queue.isEmpty()){
        
                    int j=queue.poll();
                    visited[j]=true;
                    for (int k = 0; k < l; k++) {
        
                            if (isConnected[j][k] == 1 && !visited[k]) {
        
                                queue.offer(k);
                            }
                }
            }
            circle++;
        }
        
        }
        return circle;
    }}

1.  岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。  
输入：grid = \[  
\[“1”,“1”,“1”,“1”,“0”\],  
\[“1”,“1”,“0”,“1”,“0”\],  
\[“1”,“1”,“0”,“0”,“0”\],  
\[“0”,“0”,“0”,“0”,“0”\]  
\]  
输出：1

class Solution {
        
        public int numIslands(char[][] grid) {
        
            if (grid == null || grid.length == 0) {
        
                return 0;
            }
    
            int nr = grid.length;
            int nc = grid[0].length;
            int num_islands = 0;
    
            for (int r = 0; r < nr; ++r) {
        
                for (int c = 0; c < nc; ++c) {
        
                    if (grid[r][c] == '1') {
        
                        ++num_islands;
                        grid[r][c] = '0';
                        Queue<Integer> neighbors = new LinkedList<>();
                        neighbors.add(r * nc + c);
                        while (!neighbors.isEmpty()) {
        
                            int id = neighbors.remove();
                            int row = id / nc;
                            int col = id % nc;
                            if (row - 1 >= 0 && grid[row-1][col] == '1') {
        
                                neighbors.add((row-1) * nc + col);
                                grid[row-1][col] = '0';
                            }
                            if (row + 1 < nr && grid[row+1][col] == '1') {
        
                                neighbors.add((row+1) * nc + col);
                                grid[row+1][col] = '0';
                            }
                            if (col - 1 >= 0 && grid[row][col-1] == '1') {
        
                                neighbors.add(row * nc + col-1);
                                grid[row][col-1] = '0';
                            }
                            if (col + 1 < nc && grid[row][col+1] == '1') {
        
                                neighbors.add(row * nc + col+1);
                                grid[row][col+1] = '0';
                            }
                        }
                    }
                }
            }
    
            return num_islands;
        }
    }

1.  二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格都的值都是 0 。
    路径中所有相邻的单元格应当在 **8** 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。  
输入：grid = \[\[0,1\],\[1,0\]\]  
输出：2

class Solution {
        
        public int shortestPathBinaryMatrix(int[][] grid) {
        
            if (grid[0][0] == 1) return -1;
            int res = 0, n = grid.length;
            // 存放当前元素的下标
            LinkedList<int[]> queue = new LinkedList<>();
            boolean[][] vis = new boolean[n][n];
            // 枚举8个方向
            int[][] dir = {
        {
        -1,0}, {
        -1,1}, {
        0,1},{
        1,1}, {
        1,0}, {
        1,-1}, {
        0,-1}, {
        -1,-1}};
            queue.offer(new int[]{
        0, 0});
            vis[0][0] = true;
            while (!queue.isEmpty()) {
        
                res++;
                int l = queue.size();
                for(int i = 0; i < l; i++) {
        
                    int[] t = queue.pollFirst();
                    if (t[0] == n - 1 && t[1] == n - 1) return res;
                    for (int[] d : dir) {
        
                        int x = t[0] + d[0], y = t[1] + d[1];
                        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 && !vis[x][y]) {
        
                            vis[x][y] = true;
                            queue.offer(new int[]{
        x, y});
                        }
                    }
                }
            }
            return -1;
        }
    }

一般寻找最短路径用bfs，寻找全部解用dfs。