算法基础第六天

200. 岛屿数量

这一题是用bfs来解比较方便理解的，和之前的烂番茄之类的类似的。记得要审题，这里求的是有多少个连片的岛屿。

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

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

 此外，你可以假设该网格的四条边均被水包围。



 示例 1：

 输入：grid = [
 ["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]
 ]
 输出：1
 示例 2：

 输入：grid = [
 ["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]
 ]
 输出：3


 提示：

 m == grid.length
 n == grid[i].length
 1 <= m, n <= 300
 grid[i][j] 的值为 '0' 或 '1'

 * @author zeroheart
 *
 */
public class Question200 {

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

        int res = 0;

        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    res++;
                }
            }
        }

        return res;
    }

    private void bfs(char[][] grid, int x, int y){
        int m = grid.length;
        int n = grid[0].length;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        if(x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0') return;

        grid[x][y] = '0';
        for(int i = 0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            bfs(grid, nx, ny);
        }

    }

}

547. 省份数量

这个和岛屿数量没有区别的感觉.......实际上有去区别的，是一组直接或间接相连的城市，岛屿都是直接相连的.......

/**
 547. 省份数量
 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

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

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

 返回矩阵中 省份 的数量。



 示例 1：


 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 输出：2
 示例 2：


 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
 输出：3


 提示：

 1 <= n <= 200
 n == isConnected.length
 n == isConnected[i].length
 isConnected[i][j] 为 1 或 0
 isConnected[i][i] == 1
 isConnected[i][j] == isConnected[j][i]

 * @author zeroheart
 *
 */
public class Question547 {
    public int findCircleNum(int[][] isConnected) {
        // 这个和岛屿数量没有区别的感觉.......实际上有去区别的，是一组直接或间接相连的城市，岛屿都是直接相连的.......
        int n = isConnected.length;

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList();
        int res = 0;
        for(int i = 0; i<n; i++){
            if(!visited[i]){
                res++;
                queue.add(i);

                while (!queue.isEmpty()){
                    Integer poll = queue.poll();
                    for(int x = 0; x<n; x++){
                        if(isConnected[poll][x] == 1 && !visited[x]){
                            visited[x] = true;
                            queue.add(x);
                        }
                    }
                }
            }
        }

        return res;

    }


}