。行走機器人模擬

874。行走機器人模擬

難度：中

主題：陣列、雜湊表、模擬

無限 XY 平面上的機器人從點 (0, 0) 開始，面向北。機器人可以接收這三種可能類型的命令的序列：

• -2：左轉90度。
• -1：右轉90度。
• 1

有些網格方塊是障礙物。第 i 個障礙物位於網格點障礙物[i] = (x_i, y_i)。如果機器人遇到障礙物，那麼它會留在目前位置並繼續執行下一個命令。

返回機器人從原點得到的最大歐氏距離平方（即若距離為5，則回傳25）。

注意：

• 北意味著+Y方向。
• 東意味著+X方向。
• 南意味著-Y方向。
• 西意味著-X方向。
• [0,0] 內可能有障礙物。

範例1：

• 輸入： 指令 = [4,-1,3]，障礙 = []
• 輸出： 25
• 說明：機器人從 (0, 0) 開始：
  1. 向北移動 4 個單位到 (0, 4)。
  2. 右轉。
  3. 向東移動 3 個單位到 (3, 4)。
  4. 機器人距離原點最遠的點是 (3, 4)，其平方為 32 + 42 = 25 個單位。

範例2：

• 輸入： 指令 = [4,-1,4,-2,4]，障礙 = [[2,4]]
• 輸出： 65
• 說明：機器人從 (0, 0) 開始：
  1. 向北移動 4 個單位到 (0, 4)。
  2. 右轉。
  3. 向東移動1個單位，被(2, 4)處的障礙物阻擋，機器人位於(1, 4)處。
  4. 左轉。
  5. 向北移動 4 個單位到 (1, 8)。
  6. 機器人距離原點最遠的點是 (1, 8)，其平方為 12 + 82 = 65 個單位。

範例 3：

• 輸入： 指令 = [6,-1,-1,6]，障礙 = []
• 輸出： 36
• 說明：機器人從 (0, 0) 開始：
  1. 向北移動 6 個單位到 (0, 6)。
  2. 右轉。
  3. 右轉。
  4. 向南移動 6 個單位到 (0, 0)。
  5. 機器人距離原點最遠的點是 (0, 6)，其平方為 62 = 36 個單位。

約束：

• 1 4
• 指令[i] 是 -2、-1 或 [1, 9] 範圍內的整數。
• 0 4
• -3 * 10⁴ i, y_i 4
4 答案保證小於2

31

解：

我們需要根據一系列命令在無限二維網格上模擬機器人的運動，並避開障礙物（如果有）。目標是確定機器人從原點到達的最大歐氏距離平方。

1. 方法
   方向處理
   • :
   • 機器人可以面向四個方向之一：北、東、南、西。
     我們可以將這些方向表示為向量：
     北：(0, 1)
     東：(1, 0)
     南：(0, -1)
   西：(-1, 0)

2. 轉向
   • ：
   左轉（-2）會將方向逆時針旋轉 90 度。
右轉 (-1) 會將方向順時針旋轉 90 度。

3. 運動
   • ：
對於每個移動指令，機器人都會朝當前方向移動，一次移動一個單位。如果遇到障礙物，它會根據該命令停止移動。

4. 追蹤障礙
   • ：
將障礙物清單轉換為一組元組以便快速查找，讓機器人快速判斷是否會碰到障礙物。

5. 距離計算
   • :
追蹤機器人在運動過程中到達的距原點平​​方的最大距離。

讓我們用 PHP 實作這個解決方案：

874。行走機器人模擬

<?php /**
 * @param Integer[] $commands
 * @param Integer[][] $obstacles
 * @return Integer
 */
function robotSim($commands, $obstacles) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo robotSim([4,-1,3], []) . "\n"; // Output: 25
echo robotSim([4,-1,4,-2,4], [[2,4]]) . "\n"; // Output: 65
echo robotSim([6,-1,-1,6], []) . "\n"; // Output: 36
?>

解釋：

• 方向管理：我們使用向量列表來表示方向，可以輕鬆計算移動後的下一個位置。
• 障礙物偵測：透過將障礙物儲存在集合中，我們實現了 O(1) 時間複雜度來檢查某個位置是否被障礙物阻擋。
• 距離計算：我們不斷更新機器人移動時到達的最大平方距離。

測試用例

• 提供的範例測試案例用於驗證解決方案：
  • [4,-1,3] 沒有障礙物應回傳 25。
  • [4,-1,4,-2,4] 有障礙物 [[2,4]] 應回傳 65。
  • [6,-1,-1,6] 沒有障礙物應回傳 36。

該解決方案有效地處理了問題約束並根據需要計算最大距離平方。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。行走機器人模擬的詳細內容。更多資訊請關注PHP中文網其他相關文章！