一個八數字推盤遊戲由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第一行有一整數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 |
對於每組八數字推盤遊戲,若能在14步內完成遊戲,請輸出"You can solve it within x steps.",x為解決該遊戲所需的最少移動次數。
否則,請輸出"You'd better skip this game."