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