Leetcode 200.岛屿数量 BFS

题目描述

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

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

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

思路

直接BFS求就完事了

代码

class Solution {
    
public:
    int numIslands(vector<vector<char>>& grid) {
    
        vector<vector<bool>> st(grid.size());  //标记数组
        for(int i=0;i<grid.size();i++)
            st[i].resize(grid[0].size());
        
        for(int i=0;i<grid.size();i++)         //初始化为未访问
            for(int j=0;j<grid[0].size();j++)
                st[i][j]=false;

        int res=0;  //岛屿数量

        for(int i=0;i<grid.size();i++)
            for(int j=0;j<grid[0].size();j++)
            {
    
                if(grid[i][j]=='1')
                {
    
                    if(st[i][j]) continue;
                    else
                    {
    
                        res++;
                        bfs(st,i,j,grid);  //bfs
                    }
                }
            }
        return res;
    }
    void bfs(vector<vector<bool>>& st,int x,int y,vector<vector<char>>& gap)
    {
    
        int n=gap.size(),m=gap[0].size();

        queue<pair<int,int>> q;
        q.push({
    x,y});
        st[x][y]=true;

        int dx[4]={
    -1,0,1,0},dy[4]={
    0,1,0,-1};

        while(!q.empty())
        {
    
            auto t=q.front();
            q.pop();

            for(int i=0;i<4;i++)
            {
    
                int nx=t.first+dx[i],ny=t.second+dy[i];

                if(nx<0||nx>=n||ny<0||ny>=m) continue;  //出界
                if(gap[nx][ny]=='0') continue;  //没出界，但是0
                if(st[nx][ny]) continue;   //是1，但访问过了

                q.push({
    nx,ny});
                st[nx][ny]=true;
            }
        }
    }
};