主页 讨论版 问题 名次 状态 统计
问题 G: An E-sport Player

问题 G: An E-sport Player

时间限制: 1 Sec  内存限制: 128 MB
提交: 629  解决: 94
[提交][状态][讨论版]

题目描述

    作为一个资深的E-sports player,余神酷爱打各种竞技游戏,今天他又在尝试Dota2的新模式,游戏规则是这样的:

    余神和另外八位玩家各操纵一个英雄VS,他们位于九宫格中且每名玩家占据一个位置,余神认为自己操纵的VS为0号,他将另外八位玩家的VS标号为1~8号。刚进入游戏时初始格局是随机的。

    余神操纵的VS有一个技能,他可以和相邻(上下左右)的一个VS交换,余神认为当格局为[0 1 2; 3 4 5; 6 7 8]时是优雅的。请问余神最少使用几次技能能够达到优雅的格局?如果不能到达该格局,输出“cannot”。

    例如初始格局为[1 4 2; 3 0 5; 6 7 8]时

    

    余神先和4号VS交换,再和1号VS交换便达到了优雅格局,输出2.



输入

输入第一行为一个数n,表示n组测试数据(n <= 3),接下来每三行表示其中一局游戏的初始格局。


输出

如果余神能够达到优雅格局,输出最少使用技能次数,否则输出“cannot”。

样例输入

2
1 4 2
3 0 5
6 7 8
1 4 2
3 8 5
6 7 0

样例输出

2
cannot

提示

[提交][状态][讨论版]