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. > 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 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.
