Problem Q: 29-搜索练习-棋盘游戏

Problem Q: 29-搜索练习-棋盘游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

在一个 4×44\times 44×4 的棋盘上有 888 个黑棋和 888 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。
给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。


Input

前四行，每行 444 个数字（111 或者 000），描述了初始棋盘；
接着是一个空行；
第六到第九行，每行 444 个数字（111 或者 000），描述了最终棋盘。


Output

输出文件的第一行是一个整数 nnn，表示最少的移动步数。


Sample Input

1111
0000
1110
0010

1010
0101
1010
0101

Sample Output

4

[Submit][Status]