【Hot100】LeetCode—200. 岛屿数量

• 题目连接：200. 岛屿数量

1- 思路

DFS 深搜

• 在遍历中对 res 结果进行 ++ 操作 。
• 遇到一个陆地结果为 1 的地方， 就将他们直接填充为 0

思路

• ① 先遍历，收集 res
• ② 之后通过 dfs 遇到岛屿，直接填充为 '0'

深搜三部曲

• 递归参数返回值
• 确认终止条件

2- 实现

⭐200. 岛屿数量——题解思路

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'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    public 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+1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);

    }
}

3- ACM 思路

public class numIslands {


    public static int numIsland(char[][] grid){
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;

        for(int i = 0 ; i < m ;i++){
            for(int j = 0 ; j < n;j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    public static 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+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);

    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.substring(2, input.length()-2).replace("\"","");
        String[] rows = input.split("\\],\\[");


        int m = rows.length;
        int n = rows[0].split(",").length;

        char[][] grid = new char[m][n];

        int rIndex = 0;
        for(String str : rows){
            String[] row = str.split(",");
            for(int j = 0 ;  j < n;j++){
                grid[rIndex][j] = row[j].charAt(0);
            }
            rIndex++;
        }

        System.out.println("结果是"+numIsland(grid));
    }

}