9#的做法有个地方需要修正一下：
在查询的时候才合并标记是来不及的，如下图所示：
即使合并了，s和t的颜色还是不一样，于是错误地回答“无路”了。
所以合并标记的工作必须在前期完成：
这样查询的时候就保证不会有某个点两边的标记不一样的情况了。
于是前期工作包括：
把m个障碍排序、环绕障碍并标记、把标记排序、合并标记。
这些操作的时间复杂度均为O(m*log(m))，所以前期花费仍然是O(m*log(m))的。
另外，想到一个比较好玩的东西：
1个障碍似乎可以写成4个箭头。
多个障碍可以表示成多箭头相加。
当正反向箭头重合的时候，两个箭头就互相抵消了。
如下图所示：
而加法满足交换律，所以前期就用不着把障碍排序了，直接把箭头相加就可以了。
计算结果就是我想要的环路，从而省去了把m个障碍排序的工作。
但箭头还是要排序的，所以前期工作的时间复杂度并没有变化。
想到这里，发现4楼的障碍遍历法我忽略了一道重要的工序：
必须先把障碍排序！
这样才可以从一个障碍出发然后往相邻的障碍走。
不然的话寸步难行。
例如：我站在障碍(5,8)，怎么知道(4,7)、(4,8)、(4,9)等地是不是障碍？
不排序的话，我得在整个障碍列表中检查一遍有没有(4,7)、(4,8)、(4,9)这些障碍。
排序了就可以二分查找了。
所以性能指标需要修正。
现修正如下：
性能指标预编译法障碍遍历法环绕障碍法前期花费时间O(n^2)O(m*log(m))O(m*log(m))前期花费空间O(n^2)O(m)O(m)查询花费时间O(1)O(m*log(m))O(log(m))查询花费空间O(1)O(m)O(1)地图修改维护时间O(n^2)O(m*log(m))O(log(m))地图修改维护空间O(n^2)O(m)O(m)
因为我一直以来都只用预编译法，后面的方法是看了此贴之后临时想出来的，还没有实现过。
所以难免会有疏漏之处。请大家原谅。
如果还有疏忽之处，请指正。
谢谢各位的热心帮助。
###############################
这是我的第100张贴子，做个记号，留作纪念。 呵呵，那个Smiley很吸引眼球~~ 谢谢以上各位帮忙！因为我的地图比较小，障碍较多，而且是实时变化的，我还是选了A*。 4楼的方法适合动态的障碍，而5楼的方法，对于静态的障碍，只需要建立一个2维数组，初始化一次就行了。都非常好 呵呵，不懂，顶下。 很好的题目
页:
1
[2]