主題

LeetCode - 2069. Walking Robot Simulation II 解題心得

Not In My Back Yard | 2022-05-06 00:00:10 | 巴幣 0 | 人氣 39

題目連結:


題目意譯:
一個 width × height 大小的網格坐落於一個 XY 平面上,其中左下角格子為 (0, 0) 且右上角格子為 (width - 1, height - 1)。該網格對於於四個基礎方向("North" 、 "East" 、 "South" 和 "West",即北東南西)。一機器人一開始位於格子 (0, 0) 並面朝 "East"。

機器人可以被指定去移動特定的步數。每一步,其將執行以下動作:
試圖朝著其面對的方向移動一格。
如果機器人即將走到的格子出界了,則機器人將改為執行逆時針旋轉 90 度之動作並重試剛剛的移動。

機器人執行完需求的特定步數後,其將停止並等待下一次的指令。

實作類別 Robot:
Robot(int width, int height) 初始化一個 width x height 之網格,其中機器人位於 (0, 0) 且面朝 "East"。
void step(int num) 指揮機器人向前移動 num 步。
int[] getPos() 回傳機器人當前所在之格子,格式為一個長度為 2 的陣列,即 [x, y]。
String getDir() 回傳機器人當前所面向之方位,即 "North" 、 "East" 、 "South" 或是 "West"。

限制:
2 ≦ width, height ≦ 100
1 ≦ num ≦ 10 ^ 5
最多只會有 10 ^ 4 的 step 、 getPos 和 getDir 之呼叫。



範例測資:
範例 1:
輸入
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
輸出
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
解釋
Robot robot = new Robot(6, 3); // 初始化網格,其中機器人位於 (0, 0) 且面朝東("East").
robot.move(2);  // 其往東移動兩步到 (2, 0),且面朝東。
robot.move(2);  // 其往東移動兩步到 (4, 0),且面朝東。
robot.getPos(); // 回傳 [4, 0]
robot.getDir(); // 回傳 "East"
robot.move(2);  // 其往東移動一步到 (5, 0),且面朝東。
                // 再往東走一步將會出界,因此其轉向至面朝北("North")。
                // 接著,其往北移動一步到 (5, 1),且面朝北。
robot.move(1);  // 其往北移動兩步到 (5, 2),且面朝北(而不是西("West"))。
robot.move(4);  // 再往北走一步將會出界,因此其轉向至面朝西。
                // 接著,其往西移動四步到 (1, 2),且面朝西。
robot.getPos(); // 回傳 [1, 2]
robot.getDir(); // 回傳 "West"


解題思維:
可以看到一次的 move 之呼叫可能會走很多步,所以如果每次呼叫都直接去模擬跑一次的話會超時。

但是觀察一下機器人移動的方式,可以看到機器人一直無限地走下去的話,其路徑為沿著網格的周遭繞圈之模式。也就是說,每走 2 × width + 2 × height - 4 步就會回到 (0, 0),不過值得注意的是此時機器人是面朝南(而不是一開始的朝東,下一步才會朝著東方)。

因此我們可以先模擬出這 2 × width + 2 × height - 4 步的機器人位置以及方向,然後根據每次呼叫 move 來累計當前步數(記得每 2 × width + 2 × height - 4 要歸零一次)即可得出位置以及方向。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作