Problem
A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:
-2
: turn left 90 degrees-1
: turn right 90 degrees1 <= x <= 9
: move forwardx
units
Some of the grid squares are obstacles.
The i
-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.
Example 1:
Input: commands = [4,-1,3], obstacles = [] Output: 25 Explanation: robot will go to (3, 4)
Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]] Output: 65 Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)
Note:
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
- The answer is guaranteed to be less than
2 ^ 31
.
Solution: Simulation
Time complexity: O(n + sum(x)) = O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua // Running time: 60 ms class Solution { public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { int x = 0; int y = 0; int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES int d = 1; unordered_map<int, unordered_set<int>> o; for (const auto obstacle : obstacles) o[obstacle[0]].insert(obstacle[1]); int ans = 0; for (int c : commands) { if (c == -2) d = (d - 1 + 4) % 4; else if (c == -1) d = (d + 1) % 4; else { while (c--) { int tx = x + dirs[d][0]; int ty = y + dirs[d][1]; if (o.count(tx) && o.at(tx).count(ty)) break; x = tx; y = ty; ans = max(ans, x * x + y * y); } } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment