<PREV Problem:
NEXT>
Solved by 272 users: ...
UserDateAttemptTimeCMSC
12whoami3410 sep 2012Ruby105.23250 
Darii23 oct 2010C++2501.77318 
kostya199630 jul 2014C++2501.87328 
Rizvanov15 sep 2009C++100.22347 
Darii23 oct 2010C++2601.76350 
Rizvanov15 sep 2009C++200.16369 
Philip_PV07 jul 2008C++400.68378 
MasterYoda14 oct 2010C++1701.80388 
Remag12 mar 2010C++700.77406 
Philip_PV07 jul 2008C++300.39410 
Rizvanov15 sep 2009C++300.04415 
var04 may 2007C++1301.50416 
NSI27 mar 2006C++201.88416 
Rizvanov15 sep 2009C++500.04422 
Remag12 mar 2010C++500.75422 
Rizvanov15 sep 2009C++400.04423 
frost_nova07 mar 2009C++100.80433 
Languages
C++
199
FPC
38
Java
17
Kylix
17
C
6
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

8-puzzle

Time limit = 2 second(s)

Memory limit = 10Mb

8-puzzle is analogue of the wellknown 15-puzzle. There is square region of size 3x3 with 8 square paves of size 1x1 inside. One small square inside is not paved. You can move one of the paves to the empty square.

The target position is displayed in the Figure 1.


1 2 3
4 5 6
7 8  

Figure 1. Target position.

a1 a2 a3
a4 a5 a6
a7 a8 a9

Figure 2. Order of squares in input data.

Your task is to reach target position starting with given position and make minimal number of moves.

Input. Input consists of one line with identifiers a1 a2 .. a9 corresponding to paves numbers of the position (see Fig. 2). Identifier 0 stands for empty square.

Output. Output "Yes" if given puzzle is solvable, and "No" otherwise. If "Yes" then output minimal number of moves.

Input#1
1 2 3 4 5 6 7 8 0
Output#1
Yes
0
Input#2
0 1 2 3 4 5 6 7 8 
Output#2
Yes
22

Author:
Folklor. Tests and description by Vladimir Chelnokov.
5 March 2006

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


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

SW soft NIX
ID = 3.235.66.217