<题目链接>
题目大意：
每个玩家控制一个颜色去扩张，每个颜色的扩张有自己的速度，一个颜色跑完再跑下一种颜色。在所有颜色不能在继续扩张的时候停止游戏。询问此时各种颜色的数量。
解题分析：
就是用BFS去模拟颜色的扩张，但是需要注意的是，本题需要加一些小的优化，比如，每次只用扩张上一轮BFS新更新的点就行。
#include <bits/stdc++.h>
using namespace std; #define N int(1e3+7)
#define rep(i,s,t) for(int i=s;i<=t;i++)
int n,m,p;
int sp[],prenum[];
char mpa[N][N];bool vis[N][N],go[];
typedef pair<int,int>paii;
vector<paii>vec[];
bool fp,flag;
const int dir[][]={,,,,-,,,-}; struct Node{
int x,y,s;
Node(int _x=,int _y=,int _s=):x(_x),y(_y),s(_s){}
}; void bfs(int u){
queue<Node>q;
for(int i=vec[u].size()-prenum[u];i<vec[u].size();i++){ //将该人上一轮新扩展的点全部push入列，只对这些点展开搜索，节约时间
int fi=vec[u][i].first,se=vec[u][i].second;
vis[fi][se]=true;
q.push(Node(fi,se,));
}
int num=;
while(!q.empty()){
Node now=q.front();q.pop();
int xx=now.x,yy=now.y;
if(now.s==sp[u]){ prenum[u]=num;return; } //如果步数已经走尽
for(int k=;k<;k++){
int nx=xx+dir[k][];
int ny=yy+dir[k][];
if(nx<||nx>n||ny<||ny>m||vis[nx][ny])continue;
else if(mpa[nx][ny]=='.'){ //只有碰到了'.'才能走
mpa[nx][ny]= u +'';
vec[u].push_back(paii(nx,ny)); //标记这一步已经被占领
vis[nx][ny]=true;
flag=true; //有新扩展的点
num++; //记录当前一轮push进去多少个点
q.push(Node(nx,ny,now.s+)); //将这一步push入队列
}
}
}
prenum[u]=num;
} int main(){
scanf("%d%d%d",&n,&m,&p);
rep(i,,p)scanf("%d",&sp[i]);
rep(i,,n){
scanf("%s",mpa[i]+);
rep(j,,m){
if(mpa[i][j]>=''&&mpa[i][j]<=p+''){ //如果碰到数字
vec[mpa[i][j]-''].push_back(paii(i,j)); //将该点坐标记录下
}
}
}
rep(i,,p)prenum[i]=vec[i].size(); //得到一开始各个起点的个数
memset(vis,false,sizeof(vis));
memset(go,true,sizeof(go));
while(true){ //如果有点能够一直扩展，就继续
fp=false;
for(int i=;i<=p;i++){
if(!go[i])continue;
if(go[i])flag=false,bfs(i);
if(!flag)go[i]=false; //如果这个人本轮没有走过，那么标记，下次再轮到他的时候直接跳过
if(flag)fp=true; //判断是否有人能够走
}
if(!fp)break;
}
rep(i,,p){
i==p?printf("%d\n",vec[i].size()):printf("%d ",vec[i].size());
}
}
2019-02-17