Hi,
I'll add an example, I hope that helps understanding the algorithm.
I'll take your example game field:
(the numbers are the colors of the balls)
12436531
14312262
41222432
I'll label the balls using uppercase letters:
ABCDEFGH
IJKLMNOP
QRSTUVWX
The initialisation of the union find data structure creates an array just
like the one above: every ball is in its own group and therefore the
representant of that group:
ABCDEFGH
IJKLMNOP
QRSTUVWX
Now ball A is considered. It has 3 neighbours: B, I and J. Only neighbour I
has the same color. So those two belong in the same group and a union call is
performed. Now the array looks like this:
ABCDEFGH
AJKLMNOP
QRSTUVWX
You'll notice that the I has been replaced by an A, because they both belong
to the same group. I could have chosen to replace the A by an I instead, that
doesn't make a difference.
After processing all balls in the same fashion, the resulting array looks
like this:
ABCDEFGH
ACDLMMOP
CAMMMVWP
Then the group size counting is performed, this is the resulting counters
array:
A : 3, B : 1, C : 3, D : 1, E : 1, F : 1, G : 1, H : 1
I : 0, J : 0, K : 0, L : 1, M : 5, N : 0, O : 1, P : 2
Q : 0, R : 0, S: 0, T : 0, U : 0, V : 1, W : 1, X : 0
This leads to the following "removal matrix":
01011111
00110011
00000111
Balls belonging to groups A, C and M should be removed. I noticed that your
removal matrix looks a bit different:
11011111
10110011
01000111
In this matrix, group A isn't removed. Is that a mistake in your example or
did I misunderstand your removal rule and should group A in fact not be
removed?
Bye,
Maarten
--
For info, see http://www.stack.nl/~wynke/MSX/listinfo.html
