岛屿类问题DFS

在做岛屿类问题的时候请先看作者：nettee的题解，讲的真的特别好，看了他的题解在自己做题！！！！！
链接：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

200. 岛屿数量

image.png

这道题的思路是用dfs遍历连续1的点，同时遍历的时候记得要把遍历过的1变成2，这样子后面才不会重复遍历或者进入绕圈圈的情况。
图的遍历模板就是这个：

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        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);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}

所以完整ac答案如下：

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

            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        if(!isArea(grid,i,j)){
            return ;
        }
        if(grid[i][j]!='1'){
            return;
        }
        grid[i][j] = '2';
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);

    }
    public boolean isArea(char[][] grid,int i,int j){
        return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
    }
}

695. 岛屿的最大面积

image.png

解题思路和上面的差不多，就是在dfs的时候记录一下到底有多少个1，然后保留最大值就行

 static int ans =0 ;
    static int res = 0;
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j);
                    ans = Math.max(ans,res);
                    res = 0;
                }

            }
        }
        return ans;
    }
    public void dfs(int[][] grid,int i,int j){
        if(!isArea(grid,i,j)){
            return ;
        }
        if(grid[i][j]!=1){
            return;
        }
        grid[i][j] = 2;
        res++;
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);

    }
    public boolean isArea(int[][] grid,int i,int j){
        return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
    }

463. 岛屿的周长

image.png

这道题用数学的方式做其实比用dfs来的好理解和块，但是既然是训练模板，所以还是尝试用dfs解决，这边动用了一个很巧妙的思想，就是dfs边界的问题，第一种情况是dfs到了一个1，他的其他方向没有1了，这时候返回，相当于多了一个海洋的边界；另一个情况是dfs遍历到了矩阵的四周，返回的话就一个边界的边。

class Solution {
    public int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

int dfs(int[][] grid, int r, int c) {
    // 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if (!inArea(grid, r, c)) {
        return 1;
    }
    // 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if (grid[r][c] == 0) {
        return 1;
    }
    // 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)
        + dfs(grid, r + 1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}
}