♟縱橫四海 模擬機器人的軌跡 Walking Robot Simulation_Leetcode #874

Possessed Photography on Unsplash

題目敘述 Walking Robot Simulation

機器人在一個無限大小的 X-Y 2D平面上行走，從點 (0, 0) 開始出發，一開始面向北方。

機器人可以接收以下三種類型的命令

-2 ：向左轉 90 度

-1 ：向右轉 90 度

1 <= x <= 9 ：向前移動 x 個單位長度

在網格上有一些格子被視為障礙物 obstacles 。

第 i 個障礙物位於網格點 obstacles[i] = (xi, yi) 。 機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，並繼續執行下一個命令。

請計算並且返回機器人距離原點的 最大距離 的 平方 。 （也就是說，如果距離為 5 ，則回傳 25 ）

測試範例

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: 

機器人開始位於 (0, 0)： 
1. 向北移動 4 個單位，到達 (0, 4) 
2. 右轉 
3. 向東移動 3 個單位，到達 (3, 4) 
距離原點最遠的是 (3, 4) ，距離為 3^2 + 4^2 = 25

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: 

機器人開始位於 (0, 0)：
1. 向北移動 4 個單位，到達 (0, 4)
2. 右轉
3. 向東移動 1 個單位，然後被位於 (2, 4) 的障礙物阻擋，機器人停在 (1, 4)
4. 左轉
5. 往北走 4 個單位，到達 (1, 8)
距離原點最遠的是 (1, 8) ，距離為 1^2 + 8^2 = 65

Example 3:

Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation:

機器人開始位於 (0, 0): 
1. 向北移動 6 個單位，到達 (0, 6). 
2. 右轉 
3. 右轉 
4. 向南移動 6 個單位，到達 (0, 0). 
機器人距離原點最遠的點是 (0, 6)，其距離的平方是 6^2 = 36 個單位。

約束條件

Constraints:

• 1 <= commands.length <= 10^4

指令的長度介於1~一萬。

• commands[i] is either -2, -1, or an integer in the range [1, 9].

指令內容是-2(左轉), -1(右轉) 或者1~9之間的整數。

• 0 <= obstacles.length <= 10^4

障礙物陣列的長度介於0~一萬之間。

• -3 * 10^4 <= xi, yi <= 3 * 10^4

x, y 座標都介於 負三萬~正三萬。

• The answer is guaranteed to be less than 2^31.

答案一定在4Byte整數範圍內。

演算法 根據指令模擬行進過程

指令內容是-2(左轉), -1(右轉) 或者1~9之間的整數(直接往前走k步)。

根據指令格式，判斷左轉、右轉、還是直接往前走k步。

每回合移動完之後，計算和原點的距離。

最後，回傳和原點的距離最大值的平方。

程式碼 根據指令模擬行進過程

class Solution:
    def robotSim(self, commands, obstacles):
        x, y = 0, 0
        max_dist_square, direction = 0, 0

        #                  North    West     South   East
        move, obstacles = [(0, 1), (-1, 0), (0, -1), (1, 0), ], set(map(tuple, obstacles))

        for command in commands:
            
            # Turn left
            if command == -2: direction = (direction + 1) % 4

            # Turn right
            elif command == -1: direction = (direction - 1) % 4

            else:

                # Keep moving k times
                delta_x, delta_y = move[direction]
                while command and (x + delta_x, y + delta_y) not in obstacles:
                    x += delta_x
                    y += delta_y
                    command -= 1
                    
            max_dist_square = max(max_dist_square, x ** 2 + y ** 2)

        return max_dist_square

複雜度分析

時間複雜度: O(n)

掃描每個指令一次，根據指令做出對應的行動。

空間複雜度: O(obstacle)

需要建立一個障礙物集合，所需空間為O(obstacle)

Reference

[1] Walking Robot Simulation - LeetCode