// 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;
}
Thursday, October 29, 2015
UVa 10946 - You want what filled?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment