
1 Attachment(s)
Rotating squares
My open homework about algorithms: (see attached file)
We have n * n grid squares being colored with m colors. (n >= 5; n <= 20; m <= 8))
For example (picture):
The first row displays squares’ size and color’s number.
From the second row, each row display assigned numbers for unit squares.
We define action rotation if we choose a small square in large square (small square’s size is 2k*2k) and rotate this small square by 900, 1800, 2700 angle. Of course, each unit square’s color is also changed by this action.
For example; center rotation (2,3), size 4, angle 1 ( 1 – >900, 2 – >1800, 3 – >2700)
Rotate: 2,3,4,1
The question is: finding a sequence of action rotations that make the large grid squares being separated by colors. In short, for all squares having color A we have make them become a connected block (a connected block is a chain of the squares by adjacent and not being separated).
For example:
I’ve done this homework by following method. I use BFS (breath first search) to build color blocks by spiral shape (see pictures upper). With 20*20 size and 8 colors, we must do almost 420 steps.
But I thought that this problem can be done with smaller steps’ number.
For 20*20 size, 8 colors’ case, can we do with 250 steps?
So can anyone suggest the better algorithms?