โจทย์: หุ่นยนต์เริ่มต้นที่ (0,0) หันหน้า North รับคำสั่ง: -2 (ซ้าย 90°), -1 (ขวา 90°), 1-9 (เดินหน้า x ก้าว) มี Obstacles บางตำแหน่ง หากชนจะหยุดก่อนชน หาระยะทางยุคลิดยกกำลัง 2 สูงสุดจาก Origin
Input/Output
Input: commands = [4, -1, 4, -2, 4], obstacles = [[2, 4]] Output: 65 # Path: (0,0)→(0,4)→Turn Right→(1,4)→(2,4 blocked)→Stay(1,4)→Turn Left→(1,5)→(1,6)→(1,7)→(1,8) # Max dist² = 1² + 8² = 65
อัลกอริทึม
- Direction vectors: North(0,1), East(1,0), South(0,-1), West(-1,0)
- Obstacles → Set of Tuples สำหรับ O(1) Lookup
- Simulate คำสั่งทีละตัว: หมุน หรือ เดินทีละก้าวเช็ค Obstacle
- Track max(x² + y²)
ตัวอย่างโค้ด
class Solution:
def robotSim(self, commands, obstacles):
position_offset = [(0, 1), (1, 0), (0, -1), (-1, 0)] # N, E, S, W
obstacles = set(map(tuple, obstacles))
x, y, direction, max_distance = 0, 0, 0, 0
for command in commands:
if command == -2: # Turn Left
direction = (direction - 1) % 4
elif command == -1: # Turn Right
direction = (direction + 1) % 4
else: # Move forward
dx, dy = position_offset[direction]
for _ in range(command):
if (x + dx, y + dy) not in obstacles:
x += dx
y += dy
else:
break
max_distance = max(max_distance, x*x + y*y)
return max_distance
ob = Solution()
print(ob.robotSim([4, -1, 4, -2, 4], [[2, 4]]))
ผลลัพธ์
65
Complexity: O(C + O) โดย C = ผลรวมคำสั่งเดิน, O = จำนวน Obstacles (Set Lookup O(1))
