im not an expert... but this is what i think might be possible... basically compute the manhattan distance of each piece from its current location to its final location
say for 1 5 2 4 6 3 so it will be 0 1 1 0 1 1 rest of the codes deals with manhattan distance only. find the 2x2 matrix with the largest sum, try rotate clock and anti wise, compute the result of both and check which results in a smaller sum than before and take that step. repeat till end where all is 0. this is a straight forward way... i believe there is be a much better way doing it On Friday, April 20, 2012 7:35:54 PM UTC+8, Registered user wrote: > > can anyone give some idea or hint how should i approach this problem. > how should i procceed... cant get what logic should i apply . Plz > Help..... > > thnks in advance.. > > Problem: > > Recently, with the release of the ultimate computing device bytePad, a > platform game with the simple name "Rotation Puzzle" immediately > became a phenomenon among Bytelandians. The game is extremely simple, > yet quite additive. Here's the rule: > Given a MxN rectangular grid in which each cell contains a unique > number from 1 to MxN. In each step, the player can pick any 2x2 > subgrid and perform a rotation (whether clockwise or > counterclockwise). > The task is to transform from the initial grid to the final > configuration, using as few steps as possible. > The final configuration is the configuration > 1 2 ... n > n+1 n+2 ... 2n > ... ... ... ... > (m-1)n+1 (m-1)n+2 ... mn > You may have guessed why this game is addictive: it requires a > tremendous visualization skill! > Input > > The first line contains a number T (about 5000), which is the number > of test cases. Each test case has the following form. > The first line contains two numbers M and N (2 <= M, N <= 34). > The next M lines contains the description of the grid. > Each test case's input is separated by a blank line. > It is guaranteed that each input data has a solution. > Output > > For each test case, output the result in the following format. > The first line contains a number K, the number of steps you need to > solve the puzzle. K must not exceed 10000. > Each line of the next K lines contain three numbers c, i, j (c=0 or > c=1, 1<=I < M, 1 <= J < N). (i,j) is the top-left coordinate of the > 2x2 square that is need to be rotated. c=1 if the rotation if > clockwise and c=0 if the rotation is counter-clockwise. > Prints a blank link after each test case's output. > Scoring > > Given m and n, we pick a random positive integer K* and starting from > the final configuration, we perform a random operation K* times to > generate the test case. For each test case, your score is K*/K+1. > Example > > Input: > 2 > > 2 3 > 1 5 2 > 4 6 3 > > 2 3 > 5 6 2 > 1 4 3 > > Output: > 1 > 0 1 2 > > 2 > 1 1 1 > 0 1 2 > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/vCnznBEeRRwJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
