题目描述

有一个 $3 \times 3$ 的拼图，其中放有数字 $1$ 到 $8$ 的八张卡片，并留有一个空格。每次可以把与空格上、下、左、右相邻的一张卡片移动到空格中。

给定拼图的初始状态和目标状态，请计算从初始状态变为目标状态最少需要移动多少次。如果无法变为目标状态，输出 N。

输入中的状态按照从上到下、从左到右的顺序表示，空格使用字符 # 表示。

输入格式

第一行包含一个长度为 $9$ 的字符串，表示初始状态。

第二行包含一个长度为 $9$ 的字符串，表示目标状态。

输出格式

如果能够变为目标状态，输出一个整数，表示最少移动次数；否则输出 N。

12345#678
1#2453678

2

数据范围与提示

• 两个字符串都恰好包含字符 1 到 8 和一个字符 #
• 每个字符在同一个字符串中恰好出现一次