Wednesday, April 29, 2015

UVa - 10946 - You want what filled?

#include <bits/stdc++.h>
#define S 53
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

struct data{
    char c;
    int cn;
}Letter[S*S];

string Land[S];
int cnt, x, y;
char tmp;

bool cmp(data a, data b){
    if(a.cn == b.cn)return a.c < b.c;
    return a.cn > b.cn;
}

void dfs(int i, int j){
    if(i < 0 || j < 0 || i >= x || j >= y || Land[i][j] != tmp)return;
    Land[i][j] = '.';
    cnt++;
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int main(){
    int cs = 0;
    while(cin >> x >> y){
        if(!x && !y)return 0;
        memset(Letter, 0, sizeof(Letter));
        for(int i = 0; i < x; i++)cin >> Land[i];
        int ind = 0;
        for(int i = 0; i < x; i++){
            for(int j = 0; j < y; j++){
                if(Land[i][j] != '.'){
                    cnt = 0;
                    tmp = Letter[ind].c = Land[i][j];
                    dfs(i, j);
                    Letter[ind].cn = cnt;
                    ind++;
                }
            }
        }
        sort(Letter, Letter+ind, cmp);
        printf ("Problem %d:\n", ++cs);
        for(int j = 0; j < ind; j++)cout << Letter[j].c << " " << Letter[j].cn << endl;
    }
    return 0;
}

No comments:

Post a Comment