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 步终止,将新扩展到的格子加入原队列,但是要注意的是
- 初始状态下,每个玩家可能不止拥有一个格子
- 每次搜的时候必须将所有要搜的点加入子队列,不能一个个搜,否则可能出现“挡路”情况而使后面的格子不能扩展。
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;
}
推荐阅读
-
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
-
Codeforces Round #641 (Div. 2) E. Orac and Game of Life(bfs+思维)
-
Codeforces Round #222 (Div. 2): C. Maze(BFS)
-
CodeForces 1105D 嵌套BFS
-
Codeforces contest 1064 problem D Labyrinth —— 带位置信息的bfs
-
codeforces 1064 D. Labyrinth(bfs+记忆化)
-
CodeForces 1064D Labyrinth (bfs+优先队列)
-
codeforces 1064D. Labyrinth(BFS优先队列优化)
-
【01BFS+思维】Codeforces Round #516 D. Labyrinth
-
Codeforces 676D Theseus and labyrinth 模拟+bfs