我是这样写的
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
string c;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int v[101][205],len[101];
void bfs(int a,int b){
queue<pair<int,int>> q;
q.push(make_pair(a,b));
v[a][b]=1;
while(q.size()){
auto t=q.front();q.pop();
int x=t.first,y=t.second;
for(int i=0;i<4;i++){
int x1=x+dx[i],y1=y+dy[i];
if(0<=x1&&x1<n){
if(0<=y1&&y1<len[x1]&&!v[x1][y1]){
v[x1][y1]=1;
q.push(make_pair(x1,y1));
}
}
}
}
}
int main(){
cin>>n;
getline(cin,c);
for(int i=0;i<n;i++){
getline(cin,c);
len[i]=c.length();
for(int j=0;j<len[i];j++)
if(c[j]==' '||c[j]=='*')
v[i][j]=1;
}
for(int i=0;i<n;i++)
for(int j=0;j<len[i];j++)
if(!v[i][j]){
bfs(i,j);
ans++;
}
cout<<ans;
return 0;
}
看题解有这样写的
#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;
}
二者的区别在于题解中字母是1障碍物是0,我的是障碍物1字母0(当然区别还有题解100我50),大佬们能解释一下为什么吗?