CodeForces - 1105D Kilani and the Game(多源BFS+暴力)

题目：

给出一张游戏地图和每个玩家的位置，每次能移动的步数。p个玩家轮流移动占领地图中的格子（当格子已经被占领时就不能在占领了）在每个玩家都不能移动时游戏结束。

问在游戏结束后，每个玩家占领的格子的数目。

思路：

当时做的时候，并没有思路，借鉴了大佬的……Orz

对每一个玩家分配一个队列，这个队列中只保存移动时最后一步的位置。如果在一个循环中p个玩家都没有能够成功移动的，就说明游戏结束了。

然后遍历一下地图，统计一下每个玩家占领的格子就ok了。

代码：

#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <iomanip>

#define MOD 998244353

#define MAX 1000000000

#define inf 0x3f3f3f3f

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int maxn = ;

int n,m,p;

int vis[maxn][maxn],s[maxn],ans[maxn];

int dx[]={,,,-};

int dy[]={,-,,};

char mp[maxn][maxn];

struct Node

{

    int x,y,t;

};

queue<Node> q1[maxn],q2[maxn];

bool isin(int x,int y)

{

    return x>= && x<n && y>= && y<m;

}

int MultipleBfs(int id)

{

    while(!q2[id].empty())

    {

        Node now = q2[id].front();

        q2[id].pop();

        now.t = ;//开始移动时步数都是0的，好好想想……

        q1[id].push(now);

    }

    int flag = ;

    while(!q1[id].empty())

    {

        Node now = q1[id].front();

        q1[id].pop();

        if(now.t == s[id])//记录最外围的格子的位置

        {

            q2[id].push(now);

            continue;

        }

        for(int i=; i<; i++)

        {

            int tx = now.x+dx[i],ty = now.y+dy[i];

            if(isin(tx,ty) && !vis[tx][ty] && mp[tx][ty]!='#')

            {

                vis[tx][ty] = id;

                q1[id].push(Node{tx,ty,now.t+});

                flag++;//标记这个玩家有没有移动

            }

        }

    }

    if(flag>) return ;

    else return ;

}

int main()

{

    //FRE();

    while(scanf("%d%d%d",&n,&m,&p) != EOF)

    {

        memset(ans,,sizeof(ans));

        memset(vis,,sizeof(vis));

        for(int i=; i<=p; i++) scanf("%d",&s[i]);

        for(int i=; i<n; i++)

        {

            scanf("%s",mp[i]);

            for(int j=; j<m; j++)

            {

                if(isdigit(mp[i][j]))

                {

                    int x = mp[i][j] - '';

                    vis[i][j] = x;//对每个玩家的位置进行预先标记

                    q2[x].push(Node{i,j,});//压入队列

                }

            }

        }

        while(true)

        {

            int flag = ;

            for(int i=; i<=p; i++)

            {

                flag += MultipleBfs(i);

            }

            if(!flag) break;//如果没有玩家能够移动就退出

        }

        for(int i=; i<n; i++)//统计每个玩家的格子

        {

            for(int j=; j<m; j++)

            {

                //printf("%d ",vis[i][j]);

                ans[vis[i][j]]++;

            }

            //printf("\n");

        }

        for(int i=; i<=p; i++)

        {

            if(i!=) printf(" ");

            printf("%d",ans[i]);

        }

        printf("\n");

    }

    return ;

}