游乐园的迷宫

难度: Hard

小王来到了游乐园，她玩的第一个项目是模拟推销员。有一个二维平面地图，其中散布着 N 个推销点，编号 0 到 N-1，不存在三点共线的情况。每两点之间有一条直线相连。游戏没有规定起点和终点，但限定了每次转角的方向。首先，小王需要先选择两个点分别作为起点和终点，然后从起点开始访问剩余 N-2 个点恰好一次并回到终点。访问的顺序需要满足一串给定的长度为 N-2 由 L 和 R 组成的字符串 direction，表示从起点出发之后在每个顶点上转角的方向。根据这个提示，小王希望你能够帮她找到一个可行的遍历顺序，输出顺序下标（若有多个方案，输出任意一种）。可以证明这样的遍历顺序一定是存在的。

Screenshot 2020-03-20 at 17.04.58.png

（上图：A->B->C 右转；下图：D->E->F 左转）

示例 1：

输入：points = [[1,1],[1,4],[3,2],[2,1]], direction = "LL"

输入：[0,2,1,3]

解释：[0,2,1,3] 是符合"LL"的方案之一。在 [0,2,1,3] 方案中，0->2->1 是左转方向， 2->1->3 也是左转方向

示例 2：

输入：points = [[1,3],[2,4],[3,3],[2,1]], direction = "LR"

输入：[0,3,1,2]

解释：[0,3,1,2] 是符合"LR"的方案之一。在 [0,3,1,2] 方案中，0->3->1 是左转方向， 3->1->2 是右转方向

限制：

3 <= points.length <= 1000 且 points[i].length == 2
1 <= points[i][0],points[i][1] <= 10000
direction.length == points.length - 2
direction 只包含 "L","R"

Submission

运行时间: 874 ms

内存: 16.6 MB

class Solution:
    def sub(self, a, b): # 求点 a 到点 b 的向量
        return [a[0]-b[0], a[1]-b[1]]
    def cross(self, a, b):  # 求向量 a 到向量 b 的向量叉积
        return a[0] * b[1] - a[1] * b[0]
    

    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:
        n = len(points)
        used = [False] * n  # 记录点的遍历情况， False未遍历 / True已遍历
        order = [] # 记录返回结果
        
        # 查找最左的点作为 起始点
        start = 0
        for i in range(0,n):
            if points[i][0] < points[start][0]:
                start = i
        used[start] =True
        order.append(start)
        
        for i in direction:
            nxt = -1
            if i=='L':
                # 转向方向为 L，选择相对方向最右的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) <0 :
                            nxt = j
            else:
                # 转向方向为 R，选择相对方向最左的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) >0 :
                            nxt = j
            # 返回结果加入选择的点，更新下一次转向的起点
            used[nxt] = True
            order.append(nxt)
            start = nxt
        
        # 添加最后一个剩余点
        for i in range(0,n):
            if not used[i]:
                order.append(i)
        return order

Explain

本题解采用的方法是基于模拟顺序搜索的策略，主要步骤包括：1) 找到最左侧的点作为起始点；2) 根据给定的转向指令序列依次选择下一个访问点。在选择过程中，如果当前转向指令是'L'，则从未访问的点中选择相对于当前向量方向最右侧的点；如果指令是'R'，则选择相对方向最左侧的点。这通过计算向量的叉积来判定。最后，将未访问的点添加到路径中作为终点。这种方法确保了每个点被恰好访问一次，并且满足转向的要求。

时间复杂度: O(N^2)

空间复杂度: O(N)

# 增加了注释的题解代码
class Solution:
    def sub(self, a, b): # 求点 a 到点 b 的向量
        return [a[0]-b[0], a[1]-b[1]]
    def cross(self, a, b):  # 求向量 a 到向量 b 的向量叉积
        return a[0] * b[1] - a[1] * b[0]
    
    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:
        n = len(points)
        used = [False] * n  # 记录点的遍历情况， False未遍历 / True已遍历
        order = [] # 记录返回结果
        
        # 查找最左的点作为 起始点
        start = 0
        for i in range(0,n):
            if points[i][0] < points[start][0]:
                start = i
        used[start] =True
        order.append(start)
        
        for i in direction:
            nxt = -1
            if i=='L':
                # 转向方向为 L，选择相对方向最右的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) <0 :
                            nxt = j
            else:
                # 转向方向为 R，选择相对方向最左的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) >0 :
                            nxt = j
            # 返回结果加入选择的点，更新下一次转向的起点
            used[nxt] = True
            order.append(nxt)
            start = nxt
        
        # 添加最后一个剩余点
        for i in range(0,n):
            if not used[i]:
                order.append(i)
        return order

Explore

在这种模拟顺序搜索中，选择最左侧的点作为起始点是为了确保一个固定的、可预测的起始位置，这有助于简化算法的设计和随后的路径规划。如果改变起点，算法需要适当调整以确保路径的合理性和符合转向要求。实际上，任意起点的选择都可以通过调整搜索策略（即如何选择下一个点）来实现，但这可能需要重新定义转向逻辑，以确保最终路径的有效性和连续性。终点的选择通常是所有未访问点中的最后一个，这确保了所有点都被访问一次，满足题目的完整性要求。

叉积是一个重要的几何工具，用于确定两个向量的相对方向。在二维空间中，向量A到向量B的叉积结果如果为正，则B在A的逆时针方向；如果为负，则B在A的顺时针方向。在算法中，通过计算从当前点到候选点的向量与从当前点到已选择的下一个点的向量的叉积，可以判断候选点是在当前转向方向的左侧还是右侧。这样，对于'L'的转向，我们选择叉积为负的最大值点（即最右侧），而对于'R'的转向，我们选择叉积为正的最大值点（即最左侧）。

在此题解中，始终以最近选择的点作为新的向量的起点是为了从当前位置出发，以此来确定下一步的最优选择点。这种方式能够确保路径的连续性和根据指定的转向规则（左或右）进行适当的转向。如果不以最近选择的点作为起点，路径可能会断裂或不符合转向规则，导致无法形成一条有效的、符合题目要求的访问路径。因此，这种设置对于保持算法在每一步都正确地考虑相对方向至关重要。