CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. k09
Junior Member
Join Date
Oct 2009
Posts
1

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?

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•