ahhhhh... cool... i learnt something too On Friday, April 20, 2012 9:25:38 PM UTC+8, Luke wrote: > > Each move can reduce at most four squares distance by 1. > On 20 Apr 2012 14:19, "ZuoZhong" <[email protected]> wrote: > >> oh i forgotten about A*... >> is there a reason why heuristic should be a quarter? >> >> On Friday, April 20, 2012 9:16:19 PM UTC+8, Luke wrote: >>> >>> A* algorithm using quarter of the sum of distances as a heuristic? >>> On 20 Apr 2012 13:44, "ZuoZhong" <[email protected]> wrote: >>> >>>> 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<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 google-code+unsubscribe@* >>>> *googlegroups.com <google-code%[email protected]>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/google-code?hl=en<http://groups.google.com/group/google-code?hl=en> >>>> . >>>> >>> -- >> 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/-/N8x6iH0VJT8J. >> 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. >> >
-- 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/-/pYKemZNNrV4J. 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.
