Thursday, October 29, 2015

UVa 10946 - You want what filled?

// UVa 10946 - You want what filled?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string grid[50];
int c;
int n, m;
char ch;

int move[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

struct pa {
	char ch;
	int c;
};

bool operator <(pa a, pa b) {
	return a.c > b.c || a.c == b.c && a.ch < b.ch;
}

void flood(int i, int j) {
	grid[i][j] = '.';
	c++;
	for (int k = 0; k < 4; k++) {
		int a = i + move[k][0];
		int b = j + move[k][1];
		if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == ch)
			flood(a, b);
	}
}

int main() {
	int t = 0;
	while ((cin >> n >> m) && (n || m)) {
		string dummy;
		getline(cin, dummy);
		for (int i = 0; i < n; i++)
			getline(cin, grid[i]);
		vector<pa> v;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)
				if (grid[i][j] != '.') {
					ch = grid[i][j];
					c = 0;
					flood(i, j);
					pa p = { ch, c };
					v.push_back(p);
				}
		}
		sort(v.begin(), v.end());
		t++;
		cout << "Problem " << t << ":" << endl;
		for (int i = 0; i < v.size(); i++) {
			cout << v[i].ch << " " << v[i].c << endl;
		}
	}
	return 0;
}

No comments:

Post a Comment