自动搬运

查看原文

来自洛谷，原作者为

	WxjzKK 这个人没有蓝勾，不配有个签

搬运于2025-08-24 22:20:47，当前版本为作者最后更新于2020-04-20 17:10:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题用搜索简单水过

思路：用广搜，先遍历整栋楼的的 $map$，如果不是窗户的边框 '#'，则BFS搜索出这是哪一种窗户，再给已经搜过的用 $f_i,_j$ 标记，最后输出即可。

$Code:$

#include<bits/stdc++.h> //c++专属万能头
using namespace std;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //可以走的4个方向
int num,n,m,a[6]; //a表示第i种窗户的个数，num表示在bfs函数结束后整个窗户的*的个数
char ch[502][502];
bool f[502][502]; //最多可以达到5n+1*5m+1,也就是5*100+1=501，故定义到502
struct node
{
	int x,y;
}; //定义一个结构体
void bfs(int sx,int sy) //bfs函数
{
	queue<node>que; //node类型的队列
	num=0; //num清零
	node temp;
	temp.x=sx;temp.y=sy;
	que.push(temp); //第一个入列
	f[sx][sy]=true; //这一点很容易遗漏，要把第一个点清为不可走
	if (ch[sx][sy]=='*') ++num; //记得判断第一个点是否是*号
	while (!que.empty()) //循环开始
	{
		node a=que.front();
		for (int i=0;i<4;++i) //逐个搜索每个方向
		{
			int nx=a.x+dx[i],ny=a.y+dy[i];
			if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&ch[nx][ny]!='#'&&!f[nx][ny]) //满足条件
			{
				node t;
				t.x=nx;t.y=ny;
				que.push(t); //入列
				if (ch[nx][ny]=='*') ++num; //判断
				f[nx][ny]=true; //清为不可走
			}
		}
		que.pop(); //出列
	}
}
int main()
{
	cin>>n>>m;
	n=5*n+1;m=5*m+1; //把n,m更新
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			cin>>ch[i][j];
	memset(a,0,sizeof(a)); //a数组清零
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (ch[i][j]!='#'&&!f[i][j])
			{
				bfs(i,j);++a[num/4+1]; //num/4+1就是bfs中窗户状态，不信可以去试
			}
	for (int i=1;i<=5;++i) cout<<a[i]<<' '; //输出
	return 0; //完美的结束
}