题目大意：给出一个$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 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 1005#define maxk 10const 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
         
           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
          
            Q; std::queue
           
             &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;}