This is the fifth day of my participation in Gwen Challenge

describe

A robot on an infinite XY-plane starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

  • -2: turn left 90 degrees,
  • -1: turn right 90 degrees, or
  • 1 <= k <= 9: move forward k units.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi).

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the maximum Euclidean distance that the robot will be from the origin squared (i.e. if the distance is 5, return 25).

Note:

  • North means +Y direction.
  • East means +X direction.
  • South means -Y direction.
  • West means -X direction.

Example 1:

[] Output: 25 Explanation: The robot starts at (0, 0): 1. Move north 4 units to (0, 4). 2. Turn right. 3. Move east 3 units to (3, 4). The furthest point away from the origin is (3, 4), which is 32 + 42 = 25 units away.Copy the code

Example 2:

[[2,4]] Output: 65 Explanation: The robot starts at (0, 0): 1. Move north 4 units to (0, 4). 2. Turn right. 3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4). 4. Turn left. 5. Move north 4 units to (1, 8). The furthest point away from the origin is (1, 8), which is 12 + 82 = 65 units away.Copy the code

Note:

1 <= commands. Length <= 10^4 commands[I] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9]. 0 <= obstacles.length <= 10^4 -3 * 10^4 <= xi, yi <= 3 * 10^4 The answer is guaranteed to be less than 2^31.Copy the code

parsing

Find the maximum Euclidean distance obtained by the robot after completing the route. The idea is very simple, is according to the command to locate one of the four directions, and then take a number of steps, calculate the current maximum Euclidean distance. The difficulty here is that after calculating the point, if it is an obstacle point, you have to go back to the previous point and not continue, but wait for the next command. In spite of the fact that I am lazy, I will become dizzy.

answer

class Solution(object):
    def robotSim(self, commands, obstacles):
        """
        :type commands: List[int]
        :type obstacles: List[List[int]]
        :rtype: int
        """
        position = [0, 0]
        directions = ['N', 'E', 'S', 'W']
        direction = 'N'
        max_distance = 0
        obstacles = set([(obstacle[0],obstacle[1]) for obstacle in obstacles])
        for operation in commands:
            if operation == -2:  # turn left 90 degrees,
                direction = directions[(directions.index(direction)-1)%4]
            elif operation == -1:  # -1: turn right 90 degrees
                direction = directions[(directions.index(direction)+1)%4]
            elif operation:
                for i in range(operation):
                    if direction == 'W':
                        position[0] -= 1
                        if (position[0],position[1]) in obstacles:
                            position[0] += 1
                            break
                    elif direction == 'N':
                        position[1] += 1
                        if (position[0],position[1]) in obstacles:
                            position[1] -= 1
                            break
                    elif direction == 'E':
                        position[0] += 1
                        if (position[0],position[1]) in obstacles:
                            position[0] -= 1
                            break
                    elif direction == 'S':
                        position[1] -= 1
                        if (position[0],position[1]) in obstacles:
                            position[1] += 1
                            break
                max_distance = max(position[0] ** 2 + position[1] ** 2, max_distance)
        return max_distance
        	      
		
Copy the code

The results

Given the given list in the Python online submission for Robot Simulation. Memory Usage: 10000 ms Given in the Python online submissions for Walking Robot Simulation.Copy the code

Original link: leetcode.com/problems/wa…

Your support is my biggest motivation