15-Puzzle是一个很适合打发时间的游戏。
十六片石板整齐地排列成四行四列，现在拿掉一片石板后，在任意且不重复地在剩下的每块石板上填入1到15之间的整数。
游戏开始以后，每一步都可以将一片在空格旁边的石板移到空格当中。
游戏的目标就是要把这些石板经过上述操作整齐地排列成1到15，并且空格的位置出现在右下角。
现在给你一个游戏开始时的盘面，请问最少要移动多少步才能够达到最终目标？
输入包含四行四列，一共十六个数字，代表初始盘面。其中0的位置代表空格所在。
保证输入的盘面若可达成最终目标，则答案不超过50。
请输出一个整数，代表达成目标所需操作的最少步数。如果无法达成最终目标，请输出-1。
Problem Source