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]);
}