编程题：BFS

$$N-puzzle$$是一个有很多名字和变体的拼图。在这个问题中，我们将使用15个谜题。它由一个4乘4的滑动方格组成，其中缺少一个方格。正方形用大写字母“$$A$$”到“$$O$$”标记，所需布局如下：


将拼图的“散布”定义为每个方块的当前位置与其在所需布局中的位置之间的距离之和可能很有用（例如，当使用计算机解决拼图时）。两个正方形之间的距离是它们的曼哈顿距离（两行和两列之间差值之和的绝对值）。

编写一个程序，计算给定谜题的分散度。


### 输入格式:
四行输入
每行分别包含四个字符，代表谜题的状态。

### 输出格式:
输出拼图的散度

### 输入样例:
in
ABCD
EFGH
IJKL
M.NO

### 输出样例:
out
2


### 输入样例:
in
.BCD
EAGH
IJFL
MNOK

### 输出样例:
out
6








答案：若无答案欢迎评论