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

Threaded View

  1. #1
    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?
    Attached Images Attached Images

Tags for this Thread

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured