这是一道挺有意思的题目，方法也很多，值得讨论讨论。
首先想到的是搜索的方法。
分析题目可知，9种移动方法，每种方法最多使用3次（因为4次会回到初始状态），因此总的状态数为4^9=262144，不算多，因此简单的BFS就可以搞定，但是空间开销比较大，如果牺牲一点时间换取空间，可以使用限定深度的DFS方法，将深度从1开始递增到27，搜索的状态数最多是BFS的两倍，但是空间消耗少了很多。状态表示上，可以用两个bit位表示一个钟表的状态，这样只需18位就可以表示9个钟表的状态，移动方法的作用也都采用位运算来加速。
其实这是一道数学题。
不妨设钟表的初始状态为A，9种移动方法对钟表的作用可以用矩阵M表示（第一列为第一种移动方法，依此类推），将移动方法用向量x表示，则有A + M.x = 0，于是解得x = M^{-1} * (-A)，注意所有的运算都需要模4，而M的逆可以事先求得，因此该解法的时间复杂度是O(1)，结束！
No comments:
Post a Comment