问题 2163 --棋盘游戏

2163: 棋盘游戏★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 97  解决: 76
[提交][状态][命题人:]

题目描述

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

输入

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

输出

输出文件的第一行是一个整数 nnn，表示最少的移动步数。
样例输入
Copy
1111
0000
1110
0010

1010
0101
1010
0101
样例输出
Copy
4

提示

来源

 

[提交][状态]