岛屿数量

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

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

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

看到该题我选择的方式为广度优先搜索（bfs），遍历每一个为1的点，然后从该点广度优先搜索，搜索到几个集合就代表有几个岛屿。程序代码如下：

int numIslands(vector<vector<char>>& grid) {
    if(grid.size()==0)
        return 0;
    int ans = 0;
    int x_size = grid.size(),y_size = grid.at(0).size();
    for(int i = 0; i < x_size; ++i)
    {
        for(int j = 0;j<y_size;++j)
        {
            if(grid[i][j]==‘1‘)
            {
                queue<pair<int,int>> q;
                q.push({i,j});
                grid[i][j] = ‘0‘;
                while (!q.empty())
                {
                    int x = q.front().first,y = q.front().second;
                    q.pop();

                    if(x+1<x_size&&grid[x+1][y]==‘1‘)
                    {
                        q.push({x+1, y});
                        grid[x+1][y] = ‘0‘;
                    }

                    if(y+1<y_size&&grid[x][y+1]==‘1‘)
                    {
                        q.push({x, y+1});
                        grid[x][y+1] = ‘0‘;
                    }

                    if(y-1>-1&&grid[x][y-1]==‘1‘)
                    {
                        q.push({x, y-1});
                        grid[x][y-1] = ‘0‘;
                    }

                    if(x-1>-1&&grid[x-1][y]==‘1‘)
                    {
                        q.push({x-1, y});
                        grid[x-1][y] = ‘0‘;
                    }
                }
                ans++;                 
            }
        }
    }
    return ans;
}

注意在染色的时候应该是在push进一对坐标的时候对该坐标上的点进行染色，起初我犯的错误是将顶点在pop的时候进行染色，这样的话已经被push进的顶点还有可能再次被push进队列，造成死循环导致程序出错。

岛屿数量

原文：https://www.cnblogs.com/gxyssd/p/12738731.html