SCU OJ 4445 Right Turn：2015 四川省賽模擬題（狀態記錄防死循環）

題目大意

平面上有障礙點。從原點出發，初始向右（+x）。每步嘗試向前走；若前方有障礙，則**右轉 90°** 再試，最多試 4 方向。若 4 方向皆不可走則停止。求走過的步數，若進入無限循環輸出 -1。

核心難點：無限循環檢測

狀態 = (x, y, dir)。若同一狀態出現兩次，說明進入循環。需記錄訪問過的狀態。

數據結構優化

• 對每個出現過的 x 建立 set 存儲該列的障礙 y；同理 y 映射 set 存儲該行的障礙 x。
• 查詢「當前方向前方最近障礙」轉為 set.upper_bound/lower_bound O(log n)。

代碼框架（C++，關鍵邏輯）

// 方向：0 右, 1 下, 2 左, 3 上
int dx[4] = {1,0,-1,0}, dy[4] = {0,-1,0,1};
map> col, row;  // x→y集合, y→x集合
set> vis;  // 狀態去重

while (true) {
    if (vis.count({x,y,dir})) { cout << -1; return; }
    vis.insert({x,y,dir});
    // 根據 dir 在對應 set 中查找下一障礙
    // 無障礙則按題意處理（題目保證有邊界或障礙？）
    // 移動到障礙前一格，步數+距離
    // 右轉：dir = (dir+1)%4
    // 循環直到無法移動
}

完整代碼較長，核心邏輯如上。關鍵點：

1. 離散化或 map+set 存儲稀疏障礙。
2. 狀態三元組 (x,y,dir) 去重判循環。
3. 四方向嘗試邏輯嚴格遵循「右轉優先」。

複雜度

• 時間：O(步數 * log N)，步數受狀態空間限制（O(N)）。
• 空間：O(N)。