UVa 776

From Algorithmist
Jump to navigation Jump to search

776 - Monkeys in a Regular Forest[edit]

Summary[edit]

Lots of flood fill to determine connected components.

Explanation[edit]

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 time overall to determine all of the connected regions, and another to determine which families go where. This is definitely efficient enough for this problem.

Input[edit]

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

Output[edit]

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
%