Monkeys in a Regular Forest

Consider the situation of an ideal forest, where trees grow on a regular finite euclidean lattice. At every site only one tree grows, and it can be of one among n species. Each species is denoted by a single character ({ } are valid species, for instance). Two trees of the same species are considered neighbors if the maximum absolute difference between their coordinates is one.

Families of (rather specialized) monkeys are released, one at a time, in this euclidean forest. Each family will occupy all neighboring tress of a single species which have not been taken yet by another family. The monkeys are released from left to right and from top to bottom.

Given the map of the forest, build the map of the monkeys families, starting with ``1'' and numbering them consecutively.

Input 

Input file has the lines of a matrix of single characters, separated by single blank spaces.

Next matrices (each matrix is a different instance to the problem) will be preceded by a line with a single ``%'' character and then the same structure as before.

Output 

Output file has to show lines of integers separated by as many blank spaces as required to align columns to the right.

The solution to each instance must be finished by a line with a single ``%'' character.

Sample Input 

A B D E C C D
F F W D D D D
P W E W W W W
%
a A b B c d E t
a a a a a c c t
e f g h c a a t

Sample Output 

1 2 3 4 5 5 3
6 6 7 3 3 3 3
8 7 9 7 7 7 7
%
1  2  3  4 5 6 7 8
1  1  1  1 1 5 5 8
9 10 11 12 5 1 1 8
%

---

Miguel Revilla
2000-12-30

題目很簡單，九宮格內都算相鄰。
計算 component 編號如題目描述。

#include <stdio.h>
#include <string.h>
char g[105][105];
int used[105][105];
int n, m;
void dfs(int x, int y, int label, int v) {
    if(x < 0 || y < 0 || x >= n || y >= m)
        return;
    if(g[x][y] != v || used[x][y])
        return;
    used[x][y] = label;
    dfs(x+1, y-1, label, v);
    dfs(x+1, y, label, v);
    dfs(x+1, y+1, label, v);
    dfs(x-1, y-1, label, v);
    dfs(x-1, y, label, v);
    dfs(x-1, y+1, label, v);
    dfs(x, y+1, label, v);
    dfs(x, y-1, label, v);
}
int main() {
    char s[1024];
    while(true) {
        n = 0, m;
        memset(used, 0, sizeof(used));
        int i, j, k, label = 0;
        while(gets(s)) {
            if(s[0] == '%')
                break;
            m = 0;
            for(i = 0; s[i]; i++) {
                if(s[i] != ' ')
                    g[n][m++] = s[i];
            }
            n++;
        }
        for(i = 0; i < n; i++) {
            for(j = 0; j < m; j++) {
                if(used[i][j] == 0) {
                    label++;
                    dfs(i, j, label, g[i][j]);
                }
            }
        }
        int align[105] = {};
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++) {
                int tmp = used[j][i], cnt = 0;
                while(tmp)
                    tmp = tmp/10, cnt++;
                if(align[i] < cnt)
                    align[i] = cnt;
            }
        }
        char format[50] = "%?d";
        for(i = 0; i < n; i++, puts("")) {
            for(j = 0; j < m; j++) {
                format[1] = align[j]+'0';
                if(j)
                    putchar(' ');
                printf(format, used[i][j]);
            }
        }
        puts("%");
        if(s[0] != '%')
            break;
    }
    return 0;
}