题目描述

课间，同学们在玩黑白棋的游戏，在一个 $4*4$ 的棋盘上有 $8$ 个黑棋和 $8$ 个白棋，白棋用数字 $0$ 表示，黑棋用数字 $1$ 表示。

当且仅当两个格子有公共边，这两个格子上的棋是相邻的，移动棋子的规则是交换相邻的两个棋子。

现在给出一个初始棋盘和一个最终棋盘，请你编写程序，找出一个最短的移动序列使初始棋盘变为最终棋盘。

输入格式

前四行，每行 $4$ 个数字 $(1或者0)$，描述初始棋盘；

接着是一个空行；

最后四行，每行 $4$ 个数字 $(1或者0)$，描述最终棋盘。

输出格式

一行，一个整数 n，表示最少的移动步数。

1111
0000
1110
0010

1010
0101
1010
0101

4

1010
0101
1010
0101

0110
0101
1010
0110

2

提示

数据1解释：

第一步:交换(1,2)和(2,2)

第二步:交换(1,4)和(2,4)

第三步:交换(3,2)和(4,2)

第四步:交换(4,3)和(4,4)