<PREV Problem:
NEXT>
Solved by 65 users: ...
UserDateAttemptTimeCMSC
Rizvanov29 jan 2008C++400.02570 
qinhanlei06 may 2009C++500.37621 
ethanhunt17 aug 2007C++1800.55642 
Philip_PV06 jul 2008C++1000.28655 
zard25 dec 2009C++3102.68719 
checkil23 nov 2010C++100.37740 
Olega.9023 nov 2010C++1400.37740 
oleg.dudrov06 dec 2010C++600.38740 
zard25 dec 2009C++2900.38740 
ethanhunt17 aug 2007C++1300.51754 
pmnox04 feb 2009C++3500.04838 
UdH-WiNGeR23 feb 2009Java2400.35889 
Languages
C++
44
FPC
10
Java
8
Kylix
5
C
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

15-Puzzle

Time limit = 5 second(s)

Memory limit = 33000 Kb

Solve 15-puzzle for less than 1000 moves.

1234
5678
9101112
131415 

Fig.1: Target position.

a1a2a3a4
a5a6a7a8
a9a10a11a12
a13a14a15a16

Fig.2: Initial position. ai = 0 for empty cell.

Input. Line with a1, a2, ..., a16 numbers.

Number 0 corresponds to empty cell.

Output. First line should contain YES (if solvable) or NO (if not). If YES, then second line should contain string describing moves. Moves are denoted by letters u, d, l, r (up, down, left and right). Do NOT place spaces between letters.

Input#1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
Output#1
YES

Input#2
1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12
Output#2
YES
rd

Author:
Folklor, description and tests by Eugeny Antyshev.
3 May 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.237.200.21