LeetCode 200.岛屿数量

1.题目：

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

2.代码：

dfs：

class Solution {
    public int numIslands(char[][] grid) {
        int num = 0;//计算岛屿的数量
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){//当遇到1的时候
                    num++;//岛屿数量++
                    dfs(grid,i,j);//此时用dfs把整一块岛屿的1变成0
                }
            }
        }
        return num;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]=='0') return;//递归的出口
        grid[i][j]='0';//实际操作，把1变成0
        dfs(grid,i-1,j);//这就是把水平方向和/或竖直方向上的1变成0
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
    }
}

bfs：

lass Solution {
    boolean[][] visited ;//标记访问过的节点，不要重复访问
    int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};//表示四个方向
    public int numIslands(char[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(！visited[i][j] && grid[i][j]=='1'){//这个条件始终不明白，为什么是true好奇怪
                    bfs(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }
    public void bfs(char[][] grid,int x,int y){
        Deque<int[]> queue = new ArrayDeque<>();//定义队列
        queue.offer(new int[]{x,y});//起始节点加入队列
        visited[x][y]=true;//只要加入队列，就立即标记为访问过的节点
        while(!queue.isEmpty()){//开始遍历队列里面的元素
            int[] cur = queue.poll();//把队列里的数组元素取出来
            int m = cur[0];
            int n = cur[1];
            for(int i=0;i<move.length;i++){//开始向当前结点的四个方向上下左右遍历
                int nextm = m+move[i][0];
                int nextn = n+move[i][1];//获取四个方向的坐标
                if(nextm<0 || nextn<0 || nextm>=grid.length || nextn>=grid[0].length) continue;//坐标越界了，直接跳过
                if(!visited[nextm][nextn] && grid[nextm][nextn]=='1'){//如果节点没被访问过
                    queue.offer(new int[]{nextm,nextn});//队列添加该节点为下一轮要遍历的节点
                    visited[nextm][nextn] = true;//只要加入队列立即被标记，避免重复访问
                }
            }
        }
    }
}