题解 P1767 【家族_NOI导刊2010普及（10）】

· · 题解

看各位dalao都用dfs，本蒟蒻就来发一篇bfs， 其实这题的确不难着实很坑。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
string s;
int n,cnt,l[510],a[550][550];   //最大的坑点，必须开大点，本蒟蒻开210，只有40分
void bfs(int x,int y)
{
    queue< pair<int,int> >q;    //申请队列，用pair封装，方便存取，也可以用结构体
    q.push(make_pair(x,y));
    a[x][y]=0;
    while(!q.empty())
    {
        int cx=q.front().first;     
        int cy=q.front().second;    //取队首元素
        q.pop();    //队首元素出列
        for(int i=0;i<4;i++)
        {
            int nx=cx+dx[i];
            int ny=cy+dy[i];    //向四个方向搜素
            if(nx>=1 && nx<=n && ny>=1 && ny<=l[nx] && a[nx][ny]==1)
            {
                a[nx][ny]=0;    //赋0，避免重复
                q.push(make_pair(nx,ny));   //入队列
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    getline(cin,s);
    for(int i=1;i<=n;i++)
    {
        getline(cin,s);
        l[i]=s.length();
        for(int j=1;j<=l[i];j++)
        {
            if(s[j-1]>='a' && s[j-1]<='z')
                a[i][j]=1;  //读入预处理，是字母为1，其余为0
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=l[i];j++)
        {
            if(a[i][j]==1)  //遇到字母，bfs
            {
                bfs(i,j);   
                cnt++;  //统计家族数
            }
        }
    printf("%d\n",cnt);
    return 0;
}