暂无测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出$\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

输出样例

18