LCP 3. 机器人大冒险

解题思路

将全部点投影到第一次运动循环的地图中，比较：

1. 循环数；
2. 与原点距离；

代码

class Solution:
    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:
        u=0
        r=0
#         path = [(0,0)]
        path = set()
        path.add((0,0))
        ans = False
        for c in list(command):
            if c == 'U': u+=1
            if c == 'R': r+=1
            path.add((r,u))
#         print(path,r,u)

        dist = min(x//r,y//u)  # 映射到第一个循环中
        end_point = (x-dist*r, y-dist*u)
        if end_point in path:
            ans = True
        #     print('ep in path')
        # print('d',dist, end_point)

        for ob in obstacles:
            d = min(ob[0]//r, ob[1]//u)  # 映射到第一个循环中
            xx = ob[0]-d*r
            yy = ob[1]-d*u
#             print('o',d, (xx, yy))
            if (xx, yy) in path:  # 比较达到此点的循环数
                if d < dist:
                    return False
                if d == dist:  # 若同循环数则比较谁更接近原点
                    if xx < end_point[0] and yy == end_point[1]:
                        # print('o1',d, (xx, yy))
                        return False
                    if xx == end_point[0] and yy < end_point[1]:
                        # print('o2',d, (xx, yy))
                        return False

        return ans