八数码.txt

八数码

【金凌模拟试题】:八数码

Time Limit:30000MS  Memory Limit:65536K
Total Submit:100 Accepted:48 
Case Time Limit:3000MS 

Description 

- 问题描述 
大家都熟悉得不能再熟悉的八数码问题：给定一个初始状态 
1 2 3 
4 5 6 
7 8 0 
每次可以把0和与它相邻的数字交换，问最少需要多少步，可以转换到目标状态。 



Input 

三行三个整数，分别表示了目标状态。

Output 

假如无法从初始状态到目标状态，输出一行"Impossible"(不含引号)，否则输出最少需要的步数。

Sample Input 


1 2 3
4 5 6
0 7 8


Sample Output 


2

Source