874。行走機器人模擬
難度：中
主題：陣列、雜湊表、模擬
無限 XY 平面上的機器人從點 (0, 0) 開始，面向北。機器人可以接收這三種可能類型的命令的序列：
有些網格方塊是障礙物。第 i 個障礙物位於網格點障礙物[i] = (xi, yi)。如果機器人遇到障礙物，那麼它會留在目前位置並繼續執行下一個命令。
返回機器人從原點得到的最大歐氏距離平方（即若距離為5，則回傳25）。
注意：
- 北意味著+Y方向。
- 東意味著+X方向。
- 南意味著-Y方向。
- 西意味著-X方向。
- [0,0] 內可能有障礙物。
範例1：
-
輸入： 指令 = [4,-1,3]，障礙 = []
-
輸出： 25
-
說明：機器人從 (0, 0) 開始：
- 向北移動 4 個單位到 (0, 4)。
- 右轉。
- 向東移動 3 個單位到 (3, 4)。
- 機器人距離原點最遠的點是 (3, 4)，其平方為 32 + 42 = 25 個單位。
範例2：
-
輸入： 指令 = [4,-1,4,-2,4]，障礙 = [[2,4]]
-
輸出： 65
-
說明：機器人從 (0, 0) 開始：
- 向北移動 4 個單位到 (0, 4)。
- 右轉。
- 向東移動1個單位，被(2, 4)處的障礙物阻擋，機器人位於(1, 4)處。
- 左轉。
- 向北移動 4 個單位到 (1, 8)。
- 機器人距離原點最遠的點是 (1, 8)，其平方為 12 + 82 = 65 個單位。
範例 3：
-
輸入： 指令 = [6,-1,-1,6]，障礙 = []
-
輸出： 36
- 說明：機器人從 (0, 0) 開始：
- 向北移動 6 個單位到 (0, 6)。
- 右轉。
- 右轉。
- 向南移動 6 個單位到 (0, 0)。
- 機器人距離原點最遠的點是 (0, 6)，其平方為 62 = 36 個單位。
約束：
- 1 4
-
指令[i] 是 -2、-1 或 [1, 9] 範圍內的整數。
- 0 4
- -3 * 104 i, yi 4
4
答案保證小於2
31
解：
我們需要根據一系列命令在無限二維網格上模擬機器人的運動，並避開障礙物（如果有）。目標是確定機器人從原點到達的最大歐氏距離平方。
-
方法
方向處理- :
-
機器人可以面向四個方向之一：北、東、南、西。 -
我們可以將這些方向表示為向量：
-
北：(0, 1)
-
東：(1, 0)
-
南：(0, -1)
西：(-1, 0)
-
轉向- ：
-
左轉（-2）會將方向逆時針旋轉 90 度。
右轉 (-1) 會將方向順時針旋轉 90 度。 -
對於每個移動指令，機器人都會朝當前方向移動，一次移動一個單位。如果遇到障礙物，它會根據該命令停止移動。 -
將障礙物清單轉換為一組元組以便快速查找，讓機器人快速判斷是否會碰到障礙物。 -
追蹤機器人在運動過程中到達的距原點平方的最大距離。
讓我們用 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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！
如果您想要更多類似的有用內容，請隨時關注我：
以上是。行走機器人模擬的詳細內容。更多資訊請關注PHP中文網其他相關文章！
