本题是求路径的一道题，所以是一道很明显的广度优先搜索题目，题目的条件很多：首先是要AB都到达终点，然后是要路径中AB离得尽可能的远，同时AB要尽快到达。
我们首先尝试用Hash表将所有的信息存下，然后进行搜索，我首先想到了两种构造Hash表的方法：
1、	用Hash[x1,y1,x2,y2,t]表示经过了t个时间点，A到达坐标(x1,y1)，B到达(x2,y2)，它们在途中的最近距离。
2、	用Hash[x1,y1,x2,y2,k]当A到达坐标(x1,y1)，B到达坐标(x2,y2)，它们在途中的最近距离为k时的最少时间。
　　这两种方法构造方法共同的特点是Hash表中储存了大量的信息，并且在编程实现中比较困难。
由于大量的条件在Hash表中堆积，我们尝试将其中的一个条件从Hash表中去掉，用其他的方法来分担。
假设我们已经知道了两人在途中的最近距离，那么剩下的将会简单许多。但是怎样才能知道两人在途中的最短距离呢？我们想到了二分。
在两个人在地图上的距离差最多只可能有304＝810000种可能，如果我们采用２分法，最多只需要log2810000<20次，然后在用广度优先搜索来解决剩下的问题，那么最坏的情况下扩展的节点数为20*304=16200000。完全可以在规定的时间内得出结果。
考虑到在AB移动的过程中，同一个状态(x1,y1,x2,y2)不可能出现两次，那么可以考虑直接用Hash表将状态(x1,y1,x2,y2)的情况存下，于是Hash表中应该储存下A到达坐标(x1,y1)，B到达坐标(x2,y2)，它们途中的最近距离并且在此基础上的最短时间。

小结　Hash表是非常重要的广度优先搜索优化方式之一，它能够把搜索算法的效率从大指数级提高到小指数级、多项式级甚至常数级。

上面的一段话是黄晓愉的论文上的，但是没看懂怎么回事。谁能具体讲一下啊？

• Re:大牛来讲讲这题怎么做啊 (9) zcdln 2006-11-28 16:46:34