晴天小猪历险记之Number
测试数据来自 system/1029
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
背景
话说上一回,晴天小猪不畏千难万险、千辛万苦、千磨万难……终于爬上了那座深山,来到了那位隐者的小屋中,但它不知道,有一个问题正等待着它……
晴天小猪一推开门,就发现那里……空无一人?但在屋中央有一个石桌,上面有一些字(强吧),最大的几个:如要见我,先过了这道关再说!
晴天小猪定睛一看,终于发现桌上密密麻麻布满了字,费了九天二猪之力,终于将题目看完,大意是:为了维护世界的和平……我们需要让九位勇士组成一个3*3的阵型去屠龙,但是这个阵型的要求很奇特,要九个人按照强弱依次编号1~9,且阵型中每行、每列、每条长对角线上的数字和都为15,这样才能使龙对勇士和阵型收到的损害最小,但九位勇士光是争夺名次就开始翻脸,各位**(任君想象)忙得不可开交,但晴天小猪也急得不可开交(-_-|||),只好向你求助。
描述
现在假设九位勇士已编好了号(感觉好像有人盯着我……)并站好了位置,例如:
7 8 9
1 2 3
4 5 6
每一次交换都可以将相邻的两位勇士(也就是编号……)交换位置,例如:
7 9 8
1 2 3 (8与9交换)
4 5 6
或
7 8 9
4 2 3 (4与1交换)
1 5 6
但不能
7 8 9
5 2 3 (1与5交换)
4 1 6
求最少的交换次数,使得九位勇士能在最短的时间内(当然是他们争完后……)以最安全的阵型去屠龙。
P.S:由于不能预测未来,各位设想了许多的阵型(-_-||),所以给了你10组阵型(测试点),每组50个……
格式
输入格式
输入数据一共3*50行,每个数据中用3*3的9个不同的1~9的数字表示初始状态。
(样例就只给几个阵型了^_^)
输出格式
每行一个数,即对应的初始阵型到所需阵型所需最少的交换次数,如果无解,输出-1。
样例1
样例输入1
7 8 9
1 2 3
4 5 6
6 1 8
7 5 3
2 9 4
1 2 8
3 5 4
6 7 9
样例输出1
8
0
5
限制
各个测试点5s
提示
欲知后事如何,请做出此题^_^。
来源
Sunnypig
南京师范大学2021年寒假校队训练最终赛(基础班)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2021-01-29 09:00
- 结束于
- 2021-01-29 11:30
- 持续时间
- 2.5 小时
- 主持人
- 参赛人数
- 13