目录
1. 问题描述
2. 初步分析
感觉非常没有头绪。先做一些实例计算分析。
考虑图1的{1234--3421}的例子。为了说明方便，以U*表示上边的数字，D*表示下边的数字。以“纵1”表示第一根纵线，余类推。以”横*”表示所添加的横线，横线上的数字(图中8边形中的数字)表示横线添加的序号。
假定按照类似于贪心算法的方式来绘制鬼脚图。
比如说U1要到达D1，必须横跨中间两根纵线，因此可以画出对应的横线如下图所示：
接下来考虑U2àD2. U2往下走时先碰到横1横跨到纵1，然后肯定必须再加一根横线回到纵2。但是这根横线添加的（相对于其它已经添加的横2、3的）纵向相对位置是与后续动作相关的，所以必须分情况考虑。显然这里有三种可能的情况，如下所示：
上图中的(2.1)由于横4的加入导致原来的U1到D1的路径发生了变化，所以予以排除（注1：暂时按照这种规则进行）。
图(2.2)中U2经过横1、横4后回到纵2，然后需要再添加一条横线到达D2，同样有相对于横3的上下相对位置的两种选择。但是如果添加到横3上面（横4与横3之间）的话，会导致原U1到D1的路径发生变化所以排除(2.2.1)。因此只有一种选择，如下图所示（2.2.2）：
接下来继续考虑(2.2.2)，我们会发现在(2.2.2)中U3和U4已经可以借助既有横线到达目的点了：U3-横2-横4；U4-横3-横5。因此我们得到{1234--3421}的一个鬼脚图解。
接下来再回头考虑(2.3)的继续。U2要到到达D2还要追加一条线，由于横4已经比横3低了，所以追加横5只有一种可能。如下图所示：
然后我们同样发现，在(2.3.1)中U3和U4已经可以借助既有横线到达目的点了：U3-横2-横4；U4-横3-横5。因此我们得到{1234--3421}的第二个鬼脚图解。
以上我们基于类似于贪心算法的思路得到了{1234--3421}的两个鬼脚图解。但是这里存在几个问题：
- 如何确保，或者说如何证明，以上贪心算法总能得到最优解？
- 以上鬼脚图绘制规则由人手动来做的话似乎是一目了然的，但是如何让计算机按照这个规则来搜索呢，或者说如何编程呢？
3. 代码及测试
4. 后记
[2021-11-05] 非常惭愧，这道题目从最开始看到过去了两个星期。但是一直没有找到明确的头绪，所以暂时先把到目前为止的思路列上。欢迎小伙伴们讨论指点。不过我还没有放弃（还没有想去偷看原书答案），还是希望自己能够找到一个属于自己的（哪怕笨拙）解决方案^-^毕竟现实生活中的问题并不总是有答案可以参考的。
上一篇：Q55: 平分蛋糕
下一篇：Q57: 最快的联络网
本系列总目录参见：程序员的算法趣题：详细分析和Python全解