D. Kilani and the Game(BFS模拟向四周漫延的过程)

Problem - D - Codeforces

Kilani正在和他的朋友玩一个游戏。这个游戏可以表示为一个n×m的网格，其中每个单元格都是空的或者被阻塞的，并且每个玩家在一些单元格中拥有一个或多个城堡（一个单元格中没有两个城堡）。

游戏分轮进行。每轮玩家依次扩展：首先，第一个玩家扩展，然后第二个玩家扩展，依此类推。扩展发生如下：对于每个现在拥有的城堡，玩家尝试扩展到附近的空单元格。如果从拥有他的城堡到空单元格的距离不超过si（si是玩家的扩展速度），则玩家i可以向左、上、右或下扩展，而不经过被阻塞的单元格或被其他玩家的城堡占据的单元格。玩家检查他可以扩展到的单元格集，并一次性在每个单元格中构建一个城堡。然后将回合传递给下一个玩家。

当没有玩家能够行动时，游戏结束。你将得到游戏场地和每个玩家扩展速度。Kilani想知道每个玩家在游戏结束后将控制多少个单元格（拥有一个城堡）。

输入 第一行包含三个整数n，m和p（1≤n，m≤1000，1≤p≤9）——网格的大小和玩家数量。

第二行包含p个整数si（1≤s≤109）——每个玩家扩展的速度。

接下来的n行描述了游戏网格。它们中的每一个都由m个符号组成，其中“。”表示空单元格，“#”表示阻塞单元格，数字x（1≤x≤p）表示玩家x拥有的城堡。

保证每个玩家在网格上至少有一个城堡。

输出 打印p个整数——游戏结束后每个玩家控制的单元格数。

Examples

input

Copy

3 3 2
1 1
1..
...
..2

output

Copy

6 3 

input

Copy

3 4 4
1 1 1 1
....
#...
1234

output

Copy

1 4 3 3 

题解:
题意很容易理解,假设当前玩家i的城堡有cnt个,每个城堡内的曼哈顿距离为si的都要覆盖上,

那么如何模拟这个过程呢?

每次所有已有城堡都往四周扩散一次,把旧的城堡清空,新的城堡存进来,直到没有新的城堡存入,或者扩散了si次,对于每个玩家i都是这样扩展si次,直到所有点被填充,由于每个点顶多访问1次,所以也不会超时

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 1e9 + 7;
int n,m,k;
int cnt[10];
int mp[1004][1004];
vector<PII> p[10];
int ans[10];
int dx[4] ={0,0,-1,1};
int dy[4] ={-1,1,0,0};
int f = 0;
void bfs(int x)
{vector<PII> now;while(p[x].size()){PII t = p[x].back();now.push_back(t);p[x].pop_back();}for(int j = 0;j < now.size();j++){PII t = now[j];for(int i = 0;i < 4;i++){int tx = t.first + dx[i];int ty = t.second + dy[i];if(tx >= 1&&tx <= n&&ty >= 1&&ty <= m&&!mp[tx][ty]){mp[tx][ty] = x;ans[x]++;p[x].push_back({tx,ty});}}}if(p[x].size()){f = 1;}else{f = 0;}
}
void solve()
{cin >> n >> m >> k;for(int i = 1;i <= k;i++)cin >> cnt[i];for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){char x;cin >> x;if(x == '.'){mp[i][j] = 0;continue;}else if(x == '#'){mp[i][j] = 1000;continue;}int y = x - '0';mp[i][j] = y;if(y >= 1&&y <= 9){p[y].push_back({i,j});ans[y]++;}}}while(1){int flag = 0;for(int i = 1;i <= k;i++){f = 0;for(int j = 1;j <= cnt[i];j++){bfs(i);flag = flag|f;if(!f)break;}}if(!flag)break;}for(int i = 1;i <= k;i++)cout << ans[i] <<" ";
}
//5 7 8 9 10signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}