题目大意：给出一个$n\times m(n,m\leqslant10^3)$的地图，有$k(k\leqslant9)$个玩家，第$i$个玩家速度为$s_i$。地图中$\#$代表障碍；$.$ 代表空地；数字代表是一名编号为此数字的玩家的城堡。每个玩家按编号轮流操作，每次操作把自己城堡周围$s_i$格内的空地变成自己城堡。直到没有玩家能操作为止。输出每名玩家城堡的个数。
题解：$bfs$，显然发现每个点只会扩展一次，用$k$个$queue$保存每个人的可扩展的城堡，模拟扩展即可，$s_i$可以每次扩展一格，扩展$s_i$次来解决。复杂度$O(nm)$
卡点：无
C++ Code：
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <queue>
#define maxn 1005
#define maxk 10
const int D[2][4] = {
{1, 0, -1, 0}, {0, 1, 0, -1}};
struct Point {
int x, y;
Point() { }
Point(int __x, int __y) : x(__x), y(__y) { }
} ;
std::queue<Point> q[maxk];
bool used[maxn][maxn], Continue[maxk];
int n, m, k, len[maxk], ans[maxk];
inline bool over_range(int x, int y) {
return x < 1 || x > n || y < 1 || y > m || used[x][y];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < k; ++i) scanf("%d", len + i);
for (int i = 1; i <= n; ++i) {
static char s[maxn];
scanf("%s", s + 1);
for (int j = 1; j <= m; ++j) if (s[j] != '.') {
used[i][j] = true;
if (isdigit(s[j])) {
int pos = (s[j] & 15) - 1;
++ans[pos];
q[pos].push(Point(i, j));
}
}
}
for (int now = 0, num = k; num; now += 1 - k, now += now >> 31 & k) {
static std::queue<Point> Q;
std::queue<Point> &q = ::q[now];
for (int Tim = len[now]; Tim; --Tim) {
if (q.empty()) {
num -= !Continue[now];
Continue[now] = true;
break;
}
while (!q.empty()) {
Point u = q.front(); q.pop();
for (int i = 0, x, y; i < 4; ++i) {
x = u.x + D[0][i], y = u.y + D[1][i];
if (!over_range(x, y)) {
++ans[now];
used[x][y] = true;
Q.push(Point(x, y));
}
}
}
std::swap(q, Q);
}
}
for (int i = 0; i < k; ++i) printf("%d ", ans[i]); puts("");
return 0;
}
转载于:https://www.cnblogs.com/Memory-of-winter/p/10350986.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101137.html原文链接：https://javaforall.net
