UVa 776

From Algorithmist

Contents 1 776 - Monkeys in a Regular Forest 2 Summary 3 Explanation 4 Input 5 Output

[edit] 776 - Monkeys in a Regular Forest

• http://acm.uva.es/p/v7/776.html

[edit] Summary

Lots of flood fill to determine connected components.

[edit] Explanation

A monkey family will take all trees of the same species that are connected horizontally, vertically, or diagonally. Hence we can use the flood fill algorithm to determine all of the connected components. Then, all we have to do is go through them from left to right and top to bottom. The output format is a little bit annoying, but not too difficult.

It will take O(n²) time overall to determine all of the connected regions, and another O(n²) to determine which families go where. This is definitely efficient enough for this problem.

[edit] 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

[edit] 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
%