藍橋杯 曆屆試題 九宮重排

問題描述

　　如下面第一個圖的九宮格中，放着 1~8 的數字卡片，還有一個格子空着。與空格子相鄰的格子中的卡片可以移動到空格中。經過若幹次移動，可以形成第二個圖所示的局面。

　　我們把第一個圖的局面記為：12345678.

　　把第二個圖的局面記為：123.46758

　　顯然是按從上到下，從左到右的順序記錄數字，空格記為句點。

　　本題目的任務是已知九宮的初态和終态，求最少經過多少步的移動可以到達。如果無論多少步都無法到達，則輸出-1。

輸入格式

　　輸入第一行包含九宮的初态，第二行包含九宮的終态。

輸出格式

　　輸出最少的步數，如果不存在方案，則輸出-1。

樣例輸入

12345678.

123.46758

樣例輸出

3

13524678.

46758123.

22