Leetcode_10_DFS&BFS_200岛屿数量

1.DFS

class Solution {
    private int m,n;
    public int numIslands(char[][] grid) {
        m=grid.length;
        if(m==0) return 0;
        n=grid[0].length;
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i<0||i>=m||j<0||j>=n||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);
    }
}

2.BFS

   private int m,n;
    public int numIslands(char[][] grid) {
        m=grid.length;
        if(m==0) return 0;
        n=grid[0].length;
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    bfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public void bfs(char[][] grid,int i,int j){
        Queue<int[]> queue=new LinkedList<>();
        queue.add(new int[]{i,j});
        while(!queue.isEmpty()){
        int[] cur=queue.remove();
        i=cur[0];
        j=cur[1];
        if(i>=0&&i<m&&j>=0&&j<n&&grid[i][j]=='1'){
            grid[i][j]='0';
            queue.add(new int[]{i+1,j});
            queue.add(new int[]{i-1,j});
            queue.add(new int[]{i,j+1});
            queue.add(new int[]{i,j-1});
        }
        }
    }
}