Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Solution to the n2 − 1 Puzzle
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 404Accepted: 67Special Judge

Description

In addition to the eight queen puzzle, another famous puzzle that has also been generalized is the fifteen puzzle. For a puzzle of size n × n, natural numbers below n2 are placed into squares leaving one empty. The puzzle is solved by sliding the squares until it looks similar to that shown in the figure below. Given the starting configuration, you are to find a solution or report that no solution exists.

Input

The input contains exactly one test case. The first line of input contains n (n ≤ 10). The next n2 numbers describe the puzzle by rows. The empty square is represented by zero.

Output

If no solution exists, just print “No Answer!”. Otherwise print a string consisting of the letters “L” (left), “R” (right), “U” (up), “D” (down) showing how the empty square moves to solve the puzzle.

Sample Input

2
3 1
2 0

Sample Output

LURD

Source

POJ Monthly--2007.06.03, Huang, Jinsong

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator