LeetCode 200. 岛屿数量

200. 岛屿数量

解题思路

采用深度优先搜索的方法来解决，遍历整个二维网格，当遇到一个值为 ‘1’ 的位置时，说明找到了一个岛屿。此时，我们可以通过深度优先搜索将与该位置相连的所有 ‘1’ 都标记为已访问（例如，将它们改为 ‘2’），以避免重复计数。每当我们找到一个新的岛屿时，计数器加一。

参考代码

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

    private void dfs(char[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }

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