leetcode-专题系列-BFS-岛屿数量(200)

[liuyingbin19222]

1表示岛屿，0表示海洋； 输入: 11110 11010 11000 00000

输出: 1

输入: 11000 11000 00100 00011

输出: 3

解释:岛屿的水平方向和锤子方向是水。

• idea : 可以使用并查集； 使用DFS遍历；

var dfs = function(grid,x,y){
    grid[x][y] = '0';
    var nr = grid.length;
    var nc = grid[0].length;
    if(x - 1 >= 0 && grid[x-1][y] == '1') dfs(grid,x-1,y);
    if(x + 1 < nr && grid[x+1][y] == '1') dfs(grid,x+1,y);
    if(y - 1 >= 0 && grid[x][y-1] == '1') dfs(grid,x,y-1);
    if(y + 1 < nc && grid[x][y+1] == '1') dfs(grid,x,y+1);
}
var numIslands = function(grid) {
    var queue = new Array();
    var nr = grid.length;
    if(!nr) { 
        return 0;
    }
    var nc = grid[0].length;
    var num = 0;
    for(let i = 0;i < grid.length;i++){
        for(let j = 0;j < grid[0].length;j++){
            if(grid[i][j] == '1'){
                ++num;
                dfs(grid,i,j);
            }
        }
    }
    return num;
};

使用DFS遍历岛屿图;

• 使用并查集：