题目详情 - 八数码问题 - TeMenHu

ID: 1652

传统题

1000ms

256MiB

难度: 10

上传者:

标签>

搜索

BFS

暂无测试数据。

题目描述

给出 $\red {3\times 3}$ 的九宫格，将 $\red {1\sim 8}$ 这八个自然数放入格中，输入初始状态，其中空格用数字 $\red {0}$ 表示。允许空格向它相邻的格移动，每次只能移动 $\red {1}$ 格。编程将给定的初始状态以最少步数实现从初始状态到目标状态的转换。

初始状态：

$\red {1}$	$\red { 2}$	$\red {3}$
$\red {8}$	$\red {0}$	$\red {4}$
$\red { 7}$	$\red {6}$	$\red {5}$

目标状态：

$\red {1}$	$\red {2}$	$\red {3}$
$\red {4}$	$\red {5}$	$\red {6}$
$\red {7}$	$\red {8}$	$\red {0}$

输入格式

共两行第一行为初始状态，第二行为目标状态。

输出格式

最少移动的步数。

样例

输入样例

132804765

123456780

输出样例

在下列比赛中: