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

CodeForces 1105D 嵌套BFS

程序员文章站 2022-05-24 09:09:17
...

CodeForces 1105D 嵌套BFS

题意


- 给我们一个n*m的阵列,一个格子如果是#则为障碍,若为.则为空,若为数字,则代表这个格子属于该数字代表的玩家。
- 给我们每个玩家(不到十个)的“扩张速度”,比如扩张速度为2就代表,在一回合内,该玩家可将任何与被他拥有的格子的哈密顿距离小于等于2的格子据为己有
- 每个回合按照玩家序号从小到大来扩张,只能扩张空格子,并且不能跳过格子扩张,只能“延伸”, 求最终每个玩家占领的格子数。

思路

显然是模拟跑一边bfs就行,每次将所有属于这个点的格子全部pop并且push到另一个队列里,然后在这个队列进行bfs,扩张 q i q_i qi 步终止,将新扩展到的格子加入原队列,但是要注意的是

  1. 初始状态下,每个玩家可能不止拥有一个格子
  2. 每次搜的时候必须将所有要搜的点加入子队列,不能一个个搜,否则可能出现“挡路”情况而使后面的格子不能扩展。

AC代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int n, m, q;
char ss[1005][1005];
long long aa[15];
int anss[15] = {0};
int ds[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};
struct ab
{
	int xx;
	int yy;
	int st;
}; 
vector<struct ab>aq[15];
queue<struct ab> qq;

void bfs2()
{
	struct ab start = qq.front();
	queue<struct ab> q;
	int s = start.st;
	int c = ss[start.yy][start.xx] - '0';
	while (ss[start.yy][start.xx] - '0' == c)
	{
		q.push(start);
		qq.pop();
		if (qq.empty())
		{
			break;
		}
		start = qq.front();
	}
	while (!q.empty())
	{
		start = q.front();
		q.pop();
		if (start.st - s == aa[c])
		{
			break;
		}
		int xxx = start.xx;
		int yyy = start.yy;
		for (int i = 0; i < 4; ++i)
		{
			if (yyy + ds[0][i] >= 1 && yyy + ds[0][i] <= n && xxx + ds[1][i] <= m && xxx + ds[1][i] >= 1 && ss[yyy + ds[0][i]][xxx + ds[1][i]] == '.')
			{
				struct ab dd;
				dd.xx = xxx + ds[1][i];
				dd.yy = yyy + ds[0][i];
				dd.st = start.st + 1;
				ss[yyy + ds[0][i]][xxx + ds[1][i]] = c + '0';
				q.push(dd);
				if (dd.st - s == aa[c])
				{
					qq.push(dd);
				}
				++anss[c];
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= q; ++i)
	{
		scanf("%lld", &aa[i]);
	}
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", ss[i] + 1);
		for (int j = 1; j <= m; ++j)
		{
			if (ss[i][j] >= '0' && ss[i][j] <= '9')
			{
				aq[ss[i][j] - '0'].push_back((struct ab){j, i, 0});
				++anss[ss[i][j] - '0'];
			}
		}
	}
	for (int i = 1; i <= q; ++i)
	{
		for (int j = 0; j < aq[i].size(); ++j)
		{
			qq.push(aq[i][j]);
		}
	}
	while (!qq.empty())
	{
		bfs2();
	}
	for (int i = 1; i < q; ++i)
	{
		printf("%d ", anss[i]);
	}
	if (q)
	{
		printf("%d\n", anss[q]);
	}
	return 0;
}