解題說明
Walking Robot Simulation II
題目描述： 在一個 width x height 的網格上，機器人從 (0, 0) 出發面朝東方。它沿著網格邊界行走。實作 step(num) 讓機器人走 num 步，以及 getPos() 和 getDir() 取得當前位置和方向。
解題思路： 機器人只沿邊界行走，路徑是一個週期性的環。周長 = 2 * (width - 1) + 2 * (height - 1)。
- 預計算邊界周長 perimeter = 2 * (width + height - 2)。
- 維護機器人在邊界上的線性位置 pos（0 到 perimeter-1）。
- step(num)：pos = (pos + num) % perimeter。注意：若 num 是 perimeter 的倍數且起始在原點，位置不變但方向會變（走完一圈回到原點時面朝南方）。
- 根據 pos 的值判斷在哪條邊上，推算 (x, y) 坐標和方向。
特殊處理：若 pos == 0（在原點），需要區分是初始狀態還是走了一圈回來。走了步之後在原點方向為南，初始未走過則為東。
C++ 解法
複雜度分析
時間複雜度：O(1)（每次操作）— step、getPos、getDir 都是常數時間操作。
空間複雜度：O(1) — 只存儲幾個整數變數。
虛擬碼
1. Compute perimeter = 2 * (width + height - 2). 2. Initialize pos = 0, moved = false. 3. STEP(num): pos = (pos + num) % perimeter, set moved = true. 4. GET_POS(): - If pos in [0, w-1): on bottom edge → (pos, 0). - If pos in [w-1, w+h-2): on right edge → (w-1, pos-(w-1)). - If pos in [w+h-2, 2w+h-3): on top edge → (2(w-1)+(h-1)-pos, h-1). - Else: on left edge → (0, perimeter-pos). 5. GET_DIR(): Determine direction based on which edge pos falls on. Special case: pos=0 after moving → South.
其他解法
-
直接模擬法：每步移動一格，遇到邊界轉向。時間複雜度 O(num) 每次 step 呼叫，當 num 很大時（最多 10^5 次呼叫，每次最多 10^5 步）會超時。
-
邊界座標陣列：預先將邊界上所有格子按順序存入陣列，step 時直接索引 pos % len。空間 O(perimeter) 但查詢更直覺。適用於邊界不規則的變體。
延伸思考
- 若網格有障礙物在邊界上（機器人需要跳過），如何修改邊界的環形路徑？
- 若機器人不只沿邊界走，而是可以走任意螺旋路徑，如何追蹤位置？
- 若有多個機器人同時在邊界上行走且不能重疊，如何處理碰撞？