华容道之最（六）最难的镜像玩法

要回答“最难的镜像玩法”这个问题，实在是没有什么取巧的办法，我只好老老实实把90981种布局挨个搜索一遍，最后的结果也很有意思：

最难的镜影玩法：165步，只有这一种：

最难的倒影玩法：262步；最难的反影玩法：268步，都是只有两种，而且就是三横最难的布局小兵探路和它的一个变种：

还有一个“最难”顺便也列在这里，从任意一个布局到另一个布局（可能是曹操逃出，可能是三种镜像，也可能是随便的一个别的什么）的最短路径，最长是多少呢？答案非常凑巧，就是从小兵探路走到它的反影，268步。也就是说，从任何一个布局开始，最远只能走出268步不重复的，走到269步必然绕回到之前的某一步。为什么反影刚好就是最的最短路径呢？这是一个很有趣的问题，我倾向于认为这是一个巧合，因为对于大部分的布局来说，走得最远的终局并不是反影。

等有时间我想画出一张镜影、倒影、反影、最长最短路径的曲线图来看看，应该是很有意思的。

顺便说一下，所有布局之间最长的最短路径，可以类比为图论中图的直径，求这一值并不需要挨个搜索所有的节点的最长路径。有一个办法是从任意一个布局A出发，广度优先搜索，求出从这一布局出发的最长最短路径，比如最长可以到达B，然后从B出发，再广度优先搜索一遍，比如最长到C，那么BC之间就是所有布局之间最长的最短路径了。如果A可以同时到达多个B的话，每个B都要搜一遍。能这么做的前提是所有的节点必须是连通的。这也很容易解决，可以每搜过一个布局就做一下记号，下一轮再从没做过记号里面取一个A出来，一直到所有90981种布局都做过记号。用这种办法，我原来要运行两个多小时的暴力搜索，现在只要几秒钟就出结果了。

再顺便说一下，最简单的镜影是0步，最简单的倒影是1步，这两个都很容易列举；最简单的反影则是16步，一共有8种，都是五横的布局，下面是其中之一：