10664 - easy 8 Puzzles   

Description

一個八數字推盤遊戲由3*3的棋盤組成,每一個格子上都有一個數字(0~8且不重複),一開始盤面是亂的,

1 2 3
4 0 5
7 8 6

 

每次操作可以將0與其上.下.左.右的數字互換,經過若干次操作:

step 1 : 0往右與5互換

1 2 3
4 5 0
7 8 6

step 2 : 0往下與6互換

1 2 3
4 5 6
7 8 0

 

最後將盤面排回

1 2 3
4 5 6
7 8 0

即為正解。
Rody最近沉迷於八數字推盤遊戲當中,但最近要開始期末大爆炸了,Rody不再那麼空閒,因此他決定要先跳過太過困難的題目,等到暑假再來解。

困擾的Rody想要請你幫他鑑定題目的困難度。

 

Input

input第一行有一整數T(1<=T<=30),代表底下有T筆測資。
第2~T+1行分別有9個不同的整數(0<=t1,t2,...,t9<=8),代表一個八數字推盤遊戲。

 

(註:9個整數以row major方式填入3*3的盤面,如第二組測資 1 2 3 4 0 5 7 8 6 等同於下方示意圖)

1 2 3
4 0 5
7 8 6

 

Output

對於每組八數字推盤遊戲,若能在14步內完成遊戲,請輸出"You can solve it within x steps.",x為解決該遊戲所需的最少移動次數。

否則,請輸出"You'd better skip this game."

Sample Input  Download

Sample Output  Download

Tags

happy domo



Discuss