题目描述

本题为C语言等级考试五级编程题：玩具摆放。 在4*4的方框内摆放了若干个相同的玩具，某人想通过移动玩具将其调整为目标状态。移动规则：每次只能将某一个玩具向上下左右四个方向之一移动一步，不能移出方框，且移动的目标位置不能已有玩具。请求出从初始状态到目标状态所需的最少移动次数。

• 时间限制：10000ms
• 内存限制：524288KB

输入格式

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中有玩具，0表示无玩具。接着是一个空行，接下来4行表示玩具的目标状态，格式同初始状态。

输出格式

输出一个整数，为所需的最少移动次数（题目保证初始状态可到达目标状态）。

样例输入

1111
0000
1110
0010

1010
0101
1010
0101

样例输出

4

提示

可以考虑将玩具局面表示为一个16bit的整数，设置标志数组判重，用该整数作为下标访问对应标志位。