自动搬运

查看原文

来自洛谷，原作者为

	Ksilver **

搬运于2025-08-24 21:28:52，当前版本为作者最后更新于2018-11-24 22:12:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看各位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;
}