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