提示: 欢迎访问OurACM平台。
Problem 1509 Moving Block Game

Accept: 141    Submit: 608
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

This is an interesting game consisting of eight blocks in a nine-position-square with an empty position. There is a beautiful picture broken into eight pieces with each pressed in one block. But initially, pieces of picture are ordered randomly. By moving a block up, down, left, or right to the empty place, you can make the picture recovered.

Now we use uppercase characters to denote small pieces. For example, the left diagram below denotes the initial configuration the right one below denotes the end configuration:

By moving ‘G’ left, ‘H’ down, ‘E’ left, ‘F’ up, you can make it recovered by 4 operations totally. So, giving the initial and the end configuration, please give least operations needed to recover the picture.

Input

There are multiple test cases. Each test case consists of an initial and an end configuration, each consisting of 8 distinct uppercase characters and ‘@’ specify the empty place. There is an empty line between two test cases.

Output

Output the minimum operation needed to recover the picture. If there is no solution, print -1.

Sample Input

ABC DHE @GF ABC DEF GH@ BKG FP@ CDY FBK GPD CY@

Sample Output

4 19

Source

FOJ月赛-2007年6月

Submit  Back  Status  Discuss