#2372. 九数码游戏

九数码游戏

九数码游戏

题目描述

九数码游戏 【问题描述】 这是一个很古老的游戏了:有一个3 × 3 的活动拼盘(如下图),方格上写有 0~8 这九个数字。例如: 3 7 5 2 6 1 4 8 0 利用拼盘背后的旋钮,游戏者每次可以进行以下两种操作之一: 1. 将拼盘外围的8 个方格按顺时针挪一个位置。 2. 将中间一行向右移动一个位置,最右边的方格被移到最左边。 例如: 给你一个拼盘的初始状态,你能用最少的操作次数把拼盘变成下图所示的目 标状态吗? 0 1 2 3 4 5 6 7 8 【输入文件】 输入文件中包含三行三列九个数,同行的相邻两数用空格隔开,表示初始状 37526148 0 进行操作1 23746580 1 进行操作2 23754680 1

态每个方格上的数字。初始状态不会是目标状态。 【输出文件】 如果目标状态无法达到,则输出“UNSOLVABLE”(引号不输出)。 否则,第一行是一个整数S,表示最少的操作次数。接下来4 × (S + 1)行,每 四行表示一个状态:前三行每行三个整数,相邻两数用空格隔开,表示每个方格 上的数字,第四行是一个空行,作为分隔。第一个状态必须是初始状态,最后一个 状态必须是目标状态。 【样例输入】 2 3 0 1 8 7 5 4 6 【样例输出】 4 2 3 0 1 8 7 5 4 6 1 2 3 5 8 0 4 6 7 1 2 3 0 5 8 4 6 7 0 1 2 4 5 3 6 7 8

0 1 2 3 4 5 6 7 8

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

1 2 3
5 8 0
4 6 7

1 2 3
0 5 8
4 6 7

0 1 2
4 5 3
6 7 8

0 1 2
3 4 5
6 7 8