小 Z 开锁(Unlocking the Lock)

题目描述

现在有一种新型锁，该锁是 $4\times 4$ 的矩阵，锁中有 $8$ 个凸起的格子和 $8$ 个被按下的格子，当且仅当两个格子有公共边时，称这两个格子时相邻的。

如下图所示，我们用红色填充的格子表示被按下的格子，没有填充的格子表示凸起的格子。

现在，小 Z 每一次操作只能交换两个相邻的格子，在知道初始状态和目标状态的锁之后，问小 Z 最少操作几次，才能打开这把锁。

• 打开锁，即将初始状态的锁变成目标状态。

输入格式

第 $1-4$ 行为一个 $4$ 行 $4$ 列的 $01$ 矩阵，表示初始锁的状态，$0$ 表示凸起格子，$1$ 表示被按下。

接下来有一个空行。

第 $6-9$ 行为一个 $4$ 行 $4$ 列的 $01$ 矩阵，表示目标锁的状态，$0$ 表示凸起格子，$1$ 表示被按下。

输出格式

一行一个整数表示最少操作次数。数据保证一定有解。

样例输入 #1

1111
0000
1110
0010

1010
0101
1010
0101

样例输出 #1

4

数据范围

详见题目描述与输入格式中的数据规模约定。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1300。

测试点分布

出处：原题链接