细胞

标签：int 细胞 vis second 节点 first

从一个属于某个细胞的节点且未曾访问的节点开始搜索出这节点所在的整个细胞，不断执行直到找不到这样的节点为止，执行搜索的次数即细胞个数。

“上下左右还是细胞数字则为同一细胞”从此节点的上下左右中不超过范围未曾访问还是细胞数字的则是新节点，将此节点入队，标记为已访问，拓展完所有节点后将队首出队：将队列不断执行这动作，直到队列为空，这样就能搜索到此节点所在的细胞的的所有的节点。

 

#include<iostream>
#include<string>
#include<queue>
std::string map[500];
bool vis[500][500];
bool bound(int x,int y,int m,int n)
{
    return x>=0&&y>=0&&x<m&&y<n; 
}
int dx[]={-1, 1, 0, 0};
int dy[]={ 0, 0,-1, 1};
void cell(int x,int y,int m,int n)
{
    std::queue<std::pair<int,int>> Q;
    vis[x][y]=1;
    Q.push({x,y});
    while(!Q.empty())
    {
        std::pair<int,int> u=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            std::pair<int,int> v(u.first+dx[i],u.second+dy[i]);
            if(bound(v.first,v.second,m,n)&&!vis[v.first][v.second]&&(map[v.second][v.first]!='0'))
            {
                Q.push(v);
                vis[v.first][v.second]=1;
            }
        }
    }
}
int main()
{
    int n,m;
    std::cin>>n>>m;
    for(int i=0;i<n;i++)
        std::cin>>map[i];
    int cnt=0;
    for(int y=0;y<n;y++)
        for(int x=0;x<m;x++)
            if(!vis[x][y]&&map[y][x]!='0')
            {
                cell(x,y,m,n),cnt++;
            }
    std::cout<<cnt;

} 

 

标签：int,细胞,vis,second,节点,first
From： https://www.cnblogs.com/daigemingzi/p/16619947.html