岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

给你一个由 '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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

DFS

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int[][] visited = new int[grid.length][grid[0].length];//标记该坐标是被访问过

        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == '1' && visited[i][j] == 0){//遇到了岛屿且没被访问过
                    count++;
                    dfs(grid, visited, i, j); //从坐标(i,j)开始dfs
                }
            }
        }
        return count;
    }


    public void dfs(char[][] grid, int[][] visited, int x, int y){
        //越界或者该节点已被访问，或遇到到了非岛屿，直接return
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || visited[x][y] == 1 || grid[x][y] == '0'){
            return;
        }
 
        visited[x][y] = 1; //访问该节点
        dfs(grid, visited, x - 1, y); //向上
        dfs(grid, visited, x , y - 1); //向左
        dfs(grid, visited, x + 1, y); //向下 
        dfs(grid, visited, x , y + 1); //向右

    }
}

DFS填平法，每遍历一个单位就把该单位从1变为0，即淹没掉，这样就不会重复记录该岛屿，可以不使用visited数组

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++){
        	//找到“1”，res加一，同时淹没这个岛
            if(grid[i][j] == '1'){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    return res;
}
//使用DFS“淹没”岛屿
public void dfs(char[][] grid, int i, int j){
	//搜索边界：索引越界或遍历到了"0"
    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
    //将这块土地标记为"0"
    grid[i][j] = '0';
    //根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfs
    dfs(grid,i - 1,j);
    dfs(grid,i + 1,j);
    dfs(grid,i,j + 1);
    dfs(grid,i,j - 1);
}

BFS

class Solution {
    Queue<int[]> q = new LinkedList<>();
    int[][] move = {{0, 1}, 
                    {0, -1}, 
                    {1, 0}, 
                    {-1, 0}};
    //向四个方向移动

    public int numIslands(char[][] grid) {
        int count = 0;
        int[][] visited = new int[grid.length][grid[0].length];//标记该坐标是被访问过

        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == '1' && visited[i][j] == 0){//遇到了岛屿且没被访问过,入队并访问
                    count++;
                    q.offer(new int[] {i, j});
                    visited[i][j] = 1; //访问该节点
                    bfs(grid, visited); //从坐标(i,j)开始bfs
                }
            }
        }
        return count;
    }


    public void bfs(char[][] grid, int[][] visited){

        while(!q.isEmpty()){ //队列不为空，出队,将该节点附近符合要求的节点入队并访问
            int[] pos = q.poll();
            int x = pos[0];
            int y = pos[1];

            for(int i = 0; i < 4; i++){
                int next_x = x + move[i][0];
                int next_y = y + move[i][1];
                if(next_x < 0 || next_y < 0 || next_x >= grid.length || next_y >= grid[0].length){
                    continue;
                }
                if(visited[next_x][next_y] == 0 && grid[next_x][next_y] == '1'){
                    q.offer(new int[] {next_x, next_y});
                    visited[next_x][next_y] = 1;
                }
            }
        }
    }
}