力扣200島嶼數量（DFS/BFS）

200. 島嶼數量 - 力扣（LeetCode） (leetcode-cn.com)

 1.DFS

DFS的思路是，首先周遊整個表，找到1結果就加一，之後通過DFS将找到的1連通區域内的所有1變為0，代碼如下

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

    private void dfs(char[][] grid, int i, int j, int rowlen, int collen) {
        //邊界條件
        if(i<0 || i>=rowlen || j<0 || j>=collen || grid[i][j]=='0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i+1, j, rowlen, collen);
        dfs(grid, i-1, j, rowlen, collen);
        dfs(grid, i, j+1, rowlen, collen);
        dfs(grid, i, j-1, rowlen, collen);
    }
           

BFS利用一個隊列來儲存坐标，思路相似。

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0){
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        int rowlen = grid.length;
        int collen = grid[0].length;
        int res = 0;
        for (int i = 0; i < rowlen; i++) {
            for(int j = 0;j<collen;j++){
                if(grid[i][j]=='1'){
                    res++;
                    grid[i][j] = '0';
                    queue.add(new int[]{i,j});
                    while(!queue.isEmpty()){
                        int[] cur = queue.poll();
                        if(cur[0]-1>=0 && grid[cur[0]-1][cur[1]]=='1'){
                            grid[cur[0]-1][cur[1]]='0';
                            queue.add(new int[]{cur[0]-1,cur[1]});
                        }
                        if(cur[0]+1<rowlen && grid[cur[0]+1][cur[1]]=='1'){
                            grid[cur[0]+1][cur[1]]='0';
                            queue.add(new int[]{cur[0]+1,cur[1]});
                        }
                        if(cur[1]-1>=0 && grid[cur[0]][cur[1]-1]=='1'){
                            grid[cur[0]][cur[1]-1]='0';
                            queue.add(new int[]{cur[0],cur[1]-1});
                        }
                        if(cur[1]+1<collen && grid[cur[0]][cur[1]+1]=='1'){
                            grid[cur[0]][cur[1]+1]='0';
                            queue.add(new int[]{cur[0],cur[1]+1});
                        }
                    }
                }
            }
        }
        return res;
    }
}