Rebate 200, the number of islands

力扣200,岛屿数量

题目描述

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

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

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

输入输出样例

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

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

Tips

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

解法一,使用DFS

 //encounter island problem,The main method used is graph theory,深度优先搜索DFS 和广度优先搜索 BFS
    //使用深度优先dfs ,时复 O(nm)空复 O(nm)
    int numIslands(vector<vector<char>>& grid) {
    
        //初始化值
        int islandsRow=grid.size();
        if(!islandsRow)
        {
    
            return  0;
        }

        int islandCow=grid[0].size();
        int islandNum=0;

        //Use a depth-first search to iterate over each one1的快
        for(int r=0;r<islandsRow;r++)
        {
    
            for(int c=0;c<islandCow;c++)
            {
    
                if(grid[r][c]=='1')
                {
    
                    islandNum++;
                    dfs(grid,r,c);

                }

            }
        }
        return islandNum;
    }

    void dfs(vector<vector<char>>&grid,int r,int c)
    {
    
        int islandRow=grid.size();
        int islandCow=grid[0].size();

        //Set the traversed elements to 0
        grid[r][c]='0';

        //Spread around this point,until all four sides are set to1
        if(r-1>=0&&grid[r-1][c]=='1')
            dfs(grid,r-1,c);
        if(r+1<islandRow&&grid[r+1][c]=='1')
            dfs(grid,r+1,c);
        if(c-1>=0&&grid[r][c-1]=='1')
            dfs(grid,r,c-1);
         if(c+1<islandCow&&grid[r][c+1]=='1')
            dfs(grid,r,c+1);
    }

解法二,使用BFS

 //Solution 2 uses breadth-first search
    //时复 O(nm), 空复 O(min(m,n))
    int numIslands2(vector<vector<char>>& grid) {
    
        //初始化值
        int islandsRow=grid.size();
        if(!islandsRow)
        {
    
            return  0;
        }

        int islandCow=grid[0].size();
        int islandNum=0;

        //遍历每一个结点
        for(int r=0;r<islandsRow;r++)
        {
    
            for(int c=0;c<islandCow;c++)
            {
    
                if(grid[r][c]=='1')
                {
    
                    islandNum++;
                    grid[r][c]='0';

                    //Create a queue to save
                    queue<pair<int,int>>neighbors;
                    neighbors.push({
    r,c});

                    //Use a queue to mark all sides of the node
                    while(!neighbors.empty())
                    {
    
                        auto topValue=neighbors.front();
                        neighbors.pop();
                        int row=topValue.first;
                        int col=topValue.second;

                        if(row-1>=0&&grid[row-1][col]=='1')
                        {
    
                            neighbors.push({
    row-1,col});
                            grid[row-1][col]='0';
                        }
                        if(row+1<islandsRow&&grid[row+1][col]=='1')
                        {
    
                            neighbors.push({
    row+1,col});
                            grid[row+1][col]='0';
                        }

                        if(col-1>=0&&grid[row][col-1]=='1')
                        {
    
                            neighbors.push({
    row,col-1});
                            grid[row][col-1]='0';
                        }
                        if(col+1<islandCow&&grid[row][col+1]=='1')
                        {
    
                            neighbors.push({
    row,col+1});
                            grid[row][col+1]='0';
                        }
                    }

                }
            }
        }
        return islandNum;
    }