岛屿数量

200. 岛屿数量

难度中等1041

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

class Solution {
       int[][] direction = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
        }; 
    public int numIslands(char[][] grid) {
        int row = grid.length;
        if(row == 0){
            return 0;
        }
        int count = 0;
        int col =grid[0].length;
        boolean [][] visited  = new boolean[row][col];
        for(int i = 0;i<row ;i++){
            for(int j = 0;j<col;j++){
                //没有访问过，并且是岛进入+1
                if(!visited[i][j] &&  grid[i][j]=='1'){
                    count++;
                    //扩散查找岛屿
                    dfs(i,j,visited,grid);
                }
            }
        }
        return count;



    }


    private void dfs(int x,int y,boolean[][]visited,char[][]grid){
        visited[x][y] = true;
        //每一个点都可以左右上下移动，一旦是一个岛屿，都会标记访问过，
        for(int k=0;k<4;k++){
            int nextX = x+direction[k][0];
            int nextY = y+direction[k][1];
            if(isArea(grid,nextX,nextY) && grid[nextX][nextY]=='1' && !visited[nextX][nextY] ){
                dfs(nextX,nextY,visited,grid);
            }

        }
    }

    //检测是否越界。
    private boolean isArea(char[][] grid,int row,int col){
        return row>=0 && row<grid.length && col >=0 && col < grid[0].length;
    }
}

第二种dfs:

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;
}