这道题没什么人做啊,不过的确有难度。(当时我做得时候也是看的题解)
首先,这道题和立体推箱子1的最大不同就是它给的坐标系很大。绝对不能像第一题那么做。
但同时,这个地图没有障碍物之类的东西。
这无疑给我们一些暗示,这道题应该有什么规律,可以不用跑整个bfs。
回想yxc大佬演示(玩)立体推箱子的过程。
假设到的目标很远很远,而且图中没有任何限制,那么你会怎么走。
显然,你会不断进行跨越最远的操作,直到接近目标为止。
那么什么样的操作跨越最远。
设初始状态和最终状态都是竖立的。
只要向要去的方向滚动,那么两步就能走三格。
可想而知,这是最快的方式。
所以,这道题的大体思路就是事先bfs出终点到合适范围内的最小步数,先把横坐标和纵坐标都移到和终点接近的范围内,再把两边的步数加起来。
如果初始状态不是竖立的,就把它变成竖立的,答案加上这部分步数,最后取最小值就好。
(以上思路的正确性,至少我没证明出来,只能做到感觉上是对的,希望有大佬做出更为严谨的证明或更高效准确的解法。)
%%%%%%%%%%%%%%%%
6676