黑白棋
题号：NC214864
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

黑白棋游戏的棋盘由 4×4 方格阵列构成。棋盘的每一方格中放有 1 枚棋子，共有 8 枚白棋子和 8 枚黑棋子。这 16 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 1 条公共边的 2 个方格称为相邻方格。一个方格最多可有 4 个相邻方格。在玩黑白棋游戏时，每一步可将任何 2 个相邻方格中棋子互换位置。现在给定一组初始游戏状态和目标游戏状态，计算从初始游戏状态变化到目标游戏状态的最少步数。前后分别是初始状态和目标状态。 
 1010    0011
 0101    1011
 1111    0100
 1001    1111

输入描述:

无任何输入

输出描述:

输出所需的最少步数