欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)

程序员文章站 2022-06-26 16:14:00
...

题目链接
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
题意:一开始理解错了,还以为只能向一个方向伸展,其实上下左右都可以,那么我们就用bfs宽搜,模拟即可。每次记得记录一下每个pi可以拓展的个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int maxn=1e3+5;
int n,m,p,num[maxn],Next[maxn],speed[maxn],flag;
char s[maxn][maxn];
queue<pair<int,int>>q[11];
void bfs(int x)
{
	for(int i=1;i<=speed[x];++i)//控制扩展速度 
	{
		int size=Next[x];
		Next[x]=0;
		for(int j=1;j<=size&&q[x].size()>0;++j)//控制扩展的个数 
		{
			int xx=q[x].front().first,yy=q[x].front().second;
			q[x].pop();
			for(int k=0;k<4;++k)//向四个方向深搜 
			{
				int nx=xx+dir[k][0],ny=yy+dir[k][1];
				if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]!='.') continue;
				s[nx][ny]=x+'0';
				Next[x]++;
				num[x]++;
				q[x].push({nx,ny});
			}
		}
		if(q[x].size()<=0) break;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=p;++i) scanf("%d",&speed[i]);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j)
		if(s[i][j]>='0'&&s[i][j]<='9')
		{
			int t=s[i][j]-'0';
			q[t].push({i,j});
			num[t]++;
			Next[t]++;
		}
	}
	 int flag=0;
	while(1)
	{
		flag=0;
		for(int i=1;i<=p;++i)
		{
			if(!q[i].empty()) flag=1,bfs(i);
		}
		if(!flag) break;
	}
	for(int i=1;i<=p;++i) printf("%d ",num[i]);
}