CF1105D-Kilani and the Game-（多向bfs）

http://codeforces.com/problemset/problem/1105/D

题意：有一片矩阵区域，一开始有多个势力比如1，2，3，4....9，从势力1开始轮流向外扩张，地图上为‘.’可以占领，‘#’则不能占领，被占领后不能再次被别人占领，只能上下左右扩张，每个势力有一个扩张速度，求最后整片区域上各个势力占了多少格子。

解题：

1.显然bfs，但是速度有大有小，多向bfs

2.输入的数据同一势力的起点可能不止一个（坑）

3.从势力1开始轮流扩张，不是队列一次走到头

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;


int n,m,p;
int last[10];///上一次压入了多少个点
struct node
{
    int x;
    int y;
};
int s[10];///速度
char a[1005][1005];
int vis[1005][1005];
int ans[10];
int can[10];///是否走投无路
queue<node>que[10];
int d[4][2]={ {-1,0}, {1,0}, {0,-1}, {0,1} };///上下左右

void bfs()
{
    for(int i=1;i<=p;i++)///清空
    {
        while(!que[i].empty())
            que[i].pop();
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if( a[i][j]!='.' && a[i][j]!='#' )
            {
                que[ a[i][j]-'0' ].push( {i,j} );///压入起点,可能不止一个
                vis[i][j]=a[i][j]-'0';
                last[ a[i][j]-'0' ]++;

            }
        }
    }
    bool flag=true;
    while(flag)///有人还能延伸就继续
    {
        flag=false;
        for(int idx=1;idx<=p;idx++)///每个队列走一次
        {
            for(int ss=1;ss<=s[idx] && can[idx]==0 ;ss++)///扩展速度,能走多少步,s[i]可能很大超时，用can数组截断
            {
                int num=last[idx];///本次允许弹出去扩张的节点的数量，即上次压入的节点数量
                last[idx]=0;///新一轮扩张加入的节点要清空
                for(int t=1;t<=num;t++)
                {
                    node now=que[idx].front();
                    que[idx].pop();
                    ans[idx]++;///取队头，弹出的时候区域+1
                    for(int i=0;i<4;i++)
                    {
                        int xx=now.x+d[i][0];
                        int yy=now.y+d[i][1];
                        if( xx>=0 && xx<n && yy>=0 && yy<m && vis[xx][yy]==0 && a[xx][yy]=='.' )
                        {
                            que[idx].push( {xx,yy} );
                            vis[xx][yy]=idx;///压入队列，标记访问过
                            last[idx]++;///本次压入点的个数
                        }
                    }

                }
                if(que[idx].empty())
                    can[idx]=idx;///走投无路，美德扩展了
            }
        }
        for(int i=1;i<=p;i++)
        {
            if(!que[i].empty())
                flag=true;
        }
    }
    for(int i=1;i<=p;i++)
        printf("%d ",ans[i]);
    printf("
");
}

int main()///CF1105D
{
    while(scanf("%d %d %d",&n,&m,&p)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(s,0,sizeof(s));
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        memset(last,0,sizeof(last));
        memset(can,0,sizeof(can));
        for(int i=1;i<=p;i++)///速度
            scanf("%d",&s[i]);
        getchar();
        for(int i=0;i<n;i++)///地图
            scanf("%s",a[i]);

        bfs();
    }
    return 0;
}