Monday, May 23, 2011

10946 - You want what filled?

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

char graph[M][M];
struct Hole{char ch;int dep;};

int n,X,Y;
int next[8][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct Hole H[2505];

void DFS(int,int);
bool comp(Hole,Hole);

int main()
{
    int c=1,i,j,k;
    //freopen("in.txt","r",stdin);

    while(scanf("%d%d\n",&X,&Y)&&(X|Y))
    {
        for(i=0;i<X;i++)
            gets(graph[i]);

        k = 0;
        for(i=0;i<X;i++)
            for(j=0;j<Y;j++)
                if(graph[i][j]!='.')
                {
                    n=1;
                    H[k].ch = graph[i][j];
                    DFS(i,j);
                    H[k++].dep = n;
                }
        sort(H,H+k,comp);

        printf("Problem %d:\n",c++);
        for(i=0;i<k;i++)
            printf("%c %d\n",H[i].ch,H[i].dep);
    }
    return 0;
}

void DFS(int x,int y)
{
    int tx,ty,i;
    char ch = graph[x][y];
    graph[x][y] = '.';

    for(i=0;i<8;i++)
    {
        tx = x + next[i][0];
        ty = y + next[i][1];

        if(tx>=0&&tx<X&&ty>=0&&ty<Y&&graph[tx][ty]==ch)
        {
            n++;
            DFS(tx,ty);
        }
    }
}

bool comp(Hole h1,Hole h2)
{
    if(h1.dep>h2.dep)
        return true;
    else if(h1.dep == h2.dep && h1.ch < h2.ch)
        return true;
    return false;
}

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.