【Check 66】2024-04-29 - 200. 岛屿数量

[larscheng]

200. 岛屿数量

[larscheng]

思路

• 深度优先遍历
• 参考二叉树深度遍历思想，判断badcase+向左右子树遍历
• 网格中进行深度遍历：判断badcase+向上下左右节点遍历
• 这个过程中需要注意，遍历过的节点修改状态，防止重复遍历
• 网格中的badcase即为节点超出网格

代码

class Solution {
    public int numIslands(char[][] grid) {
        int count =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);
                    count++;
                    //遍历岛屿，标记遍历状态
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return;
        }
        if (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);
    }
}

复杂度

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)