2012-05-28 13:31:12Morris
[UVA][BFS] 10946 - You want what filled?
Problem D: You want what filled?
Now that Ryan and Larry infuriated the bear, they're now forced to do menial tasks for food, one such task is filling
in potholes on this deserted island. But of course, it's never quite that easy, as the bear forces them to fill in
the biggest hole first. Since Ryan and Larry are still lazy (very little has changed, you see), can you tell them the order
to fill in the holes?
Input
The first line will contain two numbers x and y, followed by x lines of y characters each. (x and y are less than 50). The holes will be represented by the uppercase characters A to Z, and regular land will be represented by ".". There will be no other characters in the map. Input will be terminated by having 0 0 as input.Output
For each map, output the problem number (as shown below), then output the hole represented by the character, and the number of space the hole takes up, sorted by the size of the hole, break ties by sorting the characters in alphabetical order, as shown in the sample output on a separate line as shown below:Sample Input
5 5 ..AAA E.BBB ..AA. CC.DD CC.D. 5 5 ..AAA E.BBB ..AA. CC.DD CC.D. 0 0
Sample Output
Problem 1: C 4 A 3 B 3 D 3 A 2 E 1 Problem 2: C 4 A 3 B 3 D 3 A 2 E 1
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int v;
char c;
} Out;
int cmp(const void *i, const void *j) {
Out *a, *b;
a = (Out *)i, b = (Out *)j;
if(a->v != b->v)
return b->v - a->v;
return a->c - b->c;
}
int main() {
int n, m, test = 0, i, j, k, l;
char map[51][51];
Out ans[2500];
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
for(i = 0; i < n; i++)
scanf("%s", map[i]);
int used[51][51] = {}, D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int Q[2500][2], Qt, idx = 0, x, y, xx, yy;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(used[i][j] == 0 && map[i][j] != '.') {
Qt = 0, Q[0][0] = i, Q[0][1] = j, used[i][j] = 1;
for(k = 0; k <= Qt; k++) {
x = Q[k][0], y = Q[k][1];
for(l = 0; l < 4; l++) {
xx = x+D[l][0], yy = y+D[l][1];
if(xx < 0 || yy < 0 || xx >= n || yy >= m)
continue;
if(used[xx][yy] == 0 && map[i][j] == map[xx][yy]) {
Qt++;
Q[Qt][0] = xx, Q[Qt][1] = yy;
used[xx][yy] = 1;
}
}
}
ans[idx].v = Qt+1, ans[idx].c = map[i][j];
idx++;
}
}
}
qsort(ans, idx, sizeof(Out), cmp);
printf("Problem %d:\n", ++test);
for(i = 0; i < idx; i++)
printf("%c %d\n", ans[i].c, ans[i].v);
}
return 0;
}