题目描述

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

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

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

样例

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


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

算法1

(DFS) $O(n^2)$

只要找到grid[i][j] == ‘1’ 说明这就是一个岛屿，此时进入递归，递归从上下左右进行，目的就是为了探索这个岛屿的边界，在探索的过程中，只要是grid[i][j] == ‘1’ 的都是属于当前岛屿的范围，那么就把grid[i][j] == ‘2’ ，说明当前岛屿已经遍历过了，下一次不需要再遍历这个岛屿了。标记完成以后count ++ ,说明这里有一座岛。

递归终止条件：
1.(i,j) 越界
2.grid[i][j] != ‘1’ : 此时数组有3 种值: 0 ,1, 2 , 只要不等于1 说明这里要么是海水0，要么就是之前已经遍历过的岛屿2.

时间复杂度

参考文献

Java 代码

class Solution {
    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int count = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '1'){
                    dfs(grid,i,j);
                    count ++;
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid,int r,int c){
        //base case
        if(r < 0 || c < 0 || r >= grid.length || c >= grid[0].length){
            return;
        }

        if(grid[r][c] != '1') return ;

        grid[r][c] = '2';
        //上
        dfs(grid,r-1,c);
        //下
        dfs(grid,r+1,c);
        //左
        dfs(grid,r,c-1);
        //右
        dfs(grid,r,c+1);
    }
}

算法2

(BFS) $O(n^2)$

BFS 的想法就是从DFS 的一个变化。

时间复杂度

参考文献

Java 代码

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int count = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '1'){
                    bfs(grid,i,j);
                    count ++;
                }
            }
        }
        return count;
    }

    public void bfs(char[][] grid,int r,int c){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r,c});
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int i = poll[0],j = poll[1];
            if(i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == '1'){
                grid[i][j] = '2';
                queue.add(new int[]{i-1,j});
                queue.add(new int[]{i+1,j});
                queue.add(new int[]{i,j-1});
                queue.add(new int[]{i,j+1});
            }
        }
    }