题目描述

题目链接：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'

我的题解

主要思路

这道题的思路非常直观，很容易让人想到以当前坐标出发，遍历到岛屿边界，并将结果+1即可。值得注意的地方是遍历过的坐标无需再遍历，因此我们可以设置一个标识变量来记录，当然这里我就直接改变原数组，也能达到最终效果。下面以深度遍历和广度遍历两种方法实现：

方法一：深度遍历

思路

见主要思路

代码

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

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        //上
        dfs(grid, i - 1, j);
        //右
        dfs(grid, i, j + 1);
        //下
        dfs(grid, i + 1, j);
        //左
        dfs(grid, i, j - 1);
    }
}

结果

执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：49.7 MB, 在所有 Java 提交中击败了61.75%的用户

方法二：广度遍历

思路

见主要思路

代码

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

    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new ArrayDeque<>();
        grid[i][j] = '0';
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            //上
            if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                grid[x - 1][y] = '0';
                queue.offer(new int[]{x - 1, y});
            }
            //右
            if (y + 1 < grid[0].length && grid[x][y + 1] == '1') {
                grid[x][y + 1] = '0';
                queue.offer(new int[]{x, y + 1});
            }
            //下
            if (x + 1 < grid.length && grid[x + 1][y] == '1') {
                grid[x + 1][y] = '0';
                queue.offer(new int[]{x + 1, y});
            }
            //左
            if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                grid[x][y - 1] = '0';
                queue.offer(new int[]{x, y - 1});
            }
        }
    }
}