解題說明
Robot Bounded In Circle
題目描述:
一個機器人在無限平面上,初始位於原點 (0, 0) 面朝北方。給定一串指令 instructions(G = 前進一步,L = 左轉 90 度,R = 右轉 90 度),機器人會無限重複執行這串指令。判斷機器人是否被困在一個圓圈內(即不會無限遠離原點)。
解題思路: 一次模擬 + 數學判斷:
執行一輪指令後,機器人會有一個位移 (x, y) 和一個方向變化。
關鍵定理:機器人被困在圓圈內,當且僅當:
- 一輪後回到原點(位移為零),或
- 一輪後方向改變(不再面朝北)。
原因:若方向改變了,經過 2 輪(轉 180 度)或 4 輪(轉 90 度)後必定回到原點,因為位移向量會被旋轉後互相抵消。
C++ 解法
複雜度分析
時間複雜度:O(n) — 其中 n 是指令長度。只需一次遍歷。
空間複雜度:O(1) — 只使用常數個變數。
虛擬碼
1. Initialize position (x, y) = (0, 0) and direction = North. 2. For each instruction: a. 'G': move one step in current direction. b. 'L': turn left 90 degrees. c. 'R': turn right 90 degrees. 3. After one pass: If (x, y) == (0, 0) OR direction != North: return true. Else: return false.
其他解法
模擬四輪:O(4n) 時間。直接重複執行指令四次,若最終回到原點則被困。這種方法不需要數學推導但效率略低。正確性基於:任何方向變化經過 4 輪一定回到原始方向。
向量旋轉分析:用線性代數分析位移向量在旋轉下的行為。每輪的位移向量 v 經旋轉矩陣 R 變換,總位移為 v + Rv + R^2v + R^3v。若 R 不是單位矩陣,此和為零向量。
延伸思考
- 為什麼「一輪後方向改變」就能保證機器人被困?數學上如何證明位移向量的旋轉和為零?
- 如果指令中加入「後退一步」(
B),判斷條件是否需要修改? - 如果平面上有障礙物(機器人碰到障礙物不移動),問題會變得多困難?