Codeforces 616C The Labyrinth

题目链接：http://codeforces.com/problemset/problem/616/C

题意：给出n*m的矩阵，问和每一个‘*’连通的'.'有多少个(包括自己)

思路：每一个'.'连通块分配一个编号并求出连通块大小，每一个'*'号加上四周的连通块就好，注意去重

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m;
char mp[1030][1030];
int num[1030][1030],val[1000030];
int chx[5]={1,0,-1,0},chy[5]={0,-1,0,1};

void dfs(int x,int y,int cnt)
{
    if (num[x][y]!=0) return;
    num[x][y]=cnt;
    val[cnt]++;
    for (int i=0;i<4;i++)
    {
        int xx=x+chx[i];
        int yy=y+chy[i];
        if (xx<=0 || xx>n || yy<=0 || yy>m) continue;
        if (mp[xx][yy]=='*') continue;
        dfs(xx,yy,cnt);
    }
    return;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(val,0,sizeof(val));
        memset(num,0,sizeof(num));
        for (int i=1;i<=n;i++)
            scanf("%s",mp[i]+1);

        int cnt=1;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if (mp[i][j]=='.' && num[i][j]==0)
                {
                    dfs(i,j,cnt);
                    cnt++;
                }
            }
        }

        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if (mp[i][j]=='*')
                {
                    int t[5]={0},res=0;
                    t[0]=num[i+1][j];
                    t[1]=num[i][j+1];
                    t[2]=num[i-1][j];
                    t[3]=num[i][j-1];
                    sort(t,t+4);
                    for (int i=0;i<4;i++)
                        if (t[i]!=t[i+1])
                            res+=val[t[i]];
                   printf("%d",(res+1)%10);
                }
                else printf(".");

            }
            printf("\n");
        }
    }
}