<PREV Problem:
NEXT>
Solved by 272 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 = 54.224.164.166