蒟蒻的求助!!
  • 板块P1767 家族
  • 楼主Ilyinaaa
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/25 16:07
  • 上次更新2023/11/3 07:42:51
查看原帖
蒟蒻的求助!!
924189
Ilyinaaa楼主2023/7/25 16:07

我是这样写的

#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),大佬们能解释一下为什么吗?

2023/7/25 16:07
加载中...