不限时OA求助

最近收到了一个公司的OA 给了七天时间 最后一道题怎么想都TLE
题目是这样的 给你一个点的list，其实有些点被标记为起始点(用bool)。 起始点可以到任意一个x units以内的点并且起始点可以通过其他点继续移动x units。求返回一个list为所有起始点可以到达的点的index。

我的想法是先过一遍所有点 找到所有起始点并且把其他点放进hashmap<pos, index>。
然后开始BFS。对每一个队列里的点， 用一个double for loop搜索周围x unit以内所有坐标。 加入坐标在hashmap里， 我们就把他放进queue里并且记录为答案。

从起始点开始BFS是我想到的最优解了 但是还是TLE (Test case说This test many nodes spread out over a large area)。 其实这很像是一道union find的题 但是又想不到怎么用union find。
请问大家有可能优化的想法吗！！！跪地感谢！！！！

建立虚点，用并查集维护联通性。
设虚点为0号点，将0号点与所有“Spawn Point”建立联通性即可。并查集建立完成后遍历所有点，查询其是否与0号点有联通性即可。

不需要bfs，只要并查集就可以了。找一个带路径压缩的并查集代码。

1.把距离小于r的两个点union。
大致思路是x轴方向分组，y方向排序，应该可以做到NlogN。
例如把点按照横坐标丢到桶里[0, r)[r, 2r)。 对每个点只需要检查当前组，左边的组，右边的组里y值绝对值差不大于r的点。

2.把spawner跟虚点0 union（O N）
3.检查每一个点是否与虚点0联通。(O N)

如果还是TLE就是第一步写的不够好。

ymmmmm 发表于 2022-2-12 08:20
谢谢你的回答！我按照你的方法写了一遍 把2个TLE中的一个过了。还有一个TLE是有很多个点，但是只有一个sp ...

对于最后一个tle，尝试把所有点按照x坐标排序，在枚举j点找与i点毗邻的点时，用二分查找找出哪些点j满足x[i]-r<=x[j]<=x[i]+r。仅在这些点中搜索，若数据非带状密集分布，平均时间复杂度大概为O(nlogn）而非O(n^2)。
BFS剪枝：在BFS过程中，AI每跳转到一个新点就把这个点标记为可跳转，并在新点上继续跳转。如若AI要跳转的下一个点已经被标记了，这说明自己或者其他的AI已经跳转过这个点了，因此可以把这个点及其后续的路径在搜索树上删除。这就是剪枝。剪枝后可以保证每个可跳转点有且只有一次被跳转，复杂度O(n)

问题在这里: https://www.chegg.com/homework-h ... question-transcript

Google 搜索Consider A 2D Game That Uses Path Nodes For AI Navigation 第一个chegg的链接有原题

处理联通性关系的时候还可以继续优化。把所有点按照x坐标第一关键字排序。对于点(x,y)，使用二分查找确定坐标为(x',y')的点满足x-r<=x'<=x+r的条件的区间，这样所有满足联通性的点必在这个区间内。

listerily 发表于 2022-2-10 23:05
建立虚点，用并查集维护联通性。
设虚点为0号点，将0号点与所有“Spawn Point”建立联通性即可。并查集建 ...

有一种情况是 spawner -> p1 -> p2。 spawner无法直接到p2 但是可以通过p1 到p2 这种情况并查集怎么判断啊？

ymmmmm 发表于 2022-2-11 15:45
有一种情况是 spawner -> p1 -> p2。 spawner无法直接到p2 但是可以通过p1 到p2 这种情况并查集怎么判断 ...

从ADT的角度看，数据结构并查集支持以下操作：
1.初始化。
2.（内部实现）查询某个节点的“根节点”
3.将两个点联通
4.查询两个点是否联通
上述“联通”是等价关系（可传递，对称，自反）。

你使用并查集，两次执行操作3，分别是spawner-p1，p1-p2，然后执行操作4，并查集会判断出spawner与p2联通的。
如果以上无法理解，建议去学习一下并查集。
楼主在实现并查集的时候注意使用路径压缩和按秩合并。

listerily 发表于 2022-2-10 23:52
从ADT的角度看，数据结构并查集支持以下操作：
1.初始化。
2.（内部实现）查询某个节点的“根节点”

有一个地方我不是很理解 当构建完并查集后遍历点 我并不知道点跟并查集的关系 假设有点p1, p2 p3。 p1不能直接和spawner联通，那么我得先把p1储存，之后再遍历一遍不能直接遍历的list？ 这么看比bfs复杂度更高了。 就是在第一遍遍历的时候 我只能知道点跟spanwer之间是否直接能联通，还得再遍历多次才能得到最终不能联通的点。 不知道我理解的是否正确。

ymmmmm 发表于 2022-02-11 00:25:53
有一个地方我不是很理解 当构建完并查集后遍历点 我并不知道点跟并查集的关系 假设有点p1, p2 p3。 p1不能直接和spawner联通，那么我得先把p1储存，之后再遍历一遍不能直接遍历的list？

并查集是维护等价关系的数据结构。“点与并查集的关系”本身就是一个伪命题。
你在使用并查集的时候，你告诉并查集p1和p2等价，p2和p3等价。然后你再问并查集p1和p3等不等价？并查集回答你等价。一个使用了路径压缩和按秩合并的并查集是接近O(1)地回答你是否等价的，也是接近O(1)地接受你告诉他的等价信息。
注意，我并没有说并查集内部是怎么工作的，这只是介绍一个抽象的并查集概念。本题的可跳转关系就是等价关系。
再谈一谈本题的解
首先读入所有点，储存到一维数组中。每个点的ID就是该点在数组中的下标，下标为0的地方跳开。
初始化并查集
然后对于ID为1到N的所有点i，遍历其他的点j，如果i和j距离＜R，那么i和j就是可跳转的。让并查集记录这一关系。
这一操作的复杂度是O(n^2)；楼主可以考虑我的第二条回复中的优化方案，对于点稀疏的情况下能大幅优化至接近O(1)，但是最差时间复杂度仍是O(n^2)
此时并查集的等价关系已经初步建立，我们接下来建立虚点。
遍历所有spawn point ，其ID记作i。让并查集记录0和i的等价关系。
接下来，找出所有不能到达的点。遍历ID 1...N记作i，让并查集查询0和i有无等价关系。如没有，放到一个list里面。
对这个list排序。
完成。

PS：用BFS也是可以的，但是需要剪枝。BFS经过剪枝后与并查集时间复杂度一致。
对于本题，BFS剪枝或者用并查集之后时间复杂度是O(n^2)。进一步优化应该还需要我提到的x坐标排序那个方法。

listerily 发表于 2022-2-11 02:17
并查集是维护等价关系的数据结构。“点与并查集的关系”本身就是一个伪命题。
你在使用并查集的时候，你告 ...

谢谢你的回答！我按照你的方法写了一遍 把2个TLE中的一个过了。还有一个TLE是有很多个点，但是只有一个spawner。 对于这种情况，实在想不到如何优化了。


补充内容 (2022-02-12 11:34 +8:00):
还想请教一下，如何对bfs进行剪枝以避免重复？