Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/874.html
874. Walking Robot Simulation (Easy)
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 forwardxunits
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 <= 100000 <= obstacles.length <= 10000-30000 <= obstacle[i][0] <= 30000-30000 <= obstacle[i][1] <= 30000- The answer is guaranteed to be less than
2 ^ 31.
Companies: Jane Street
Related Topics: Greedy
Solution 1.
Notice that the question asks for the maximum distance, not the final distance.
// OJ: https://leetcode.com/problems/walking-robot-simulation/
// Time: O(C)
// Space: O(O)
class Solution {
private:
long long hash(int x, int y) {
return (long long)(x + 30000) * 100000 + y + 30000;
}
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<long long> obs;
for (auto &ob : obstacles) obs.insert(hash(ob[0], ob[1]));
int ans = 0, x = 0, y = 0, dir = 0; // 0=N, 1=W, 2=S, 3=E
int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };
for (int cmd : commands) {
if (cmd == -2) {
dir = (dir + 1) % 4;
} else if (cmd == -1) {
dir = (dir + 3) % 4;
} else {
auto &d = dirs[dir];
while (cmd--) {
if (obs.find(hash(x + d[0], y + d[1])) != obs.end()) break;
x += d[0];
y += d[1];
ans = max(ans, x * x + y * y);
}
}
}
return ans;
}
};
-
class Solution { public int robotSim(int[] commands, int[][] obstacles) { int[][] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int directionIndex = 0; Map<Integer, List<Integer>> obstaclesEachX = new HashMap<Integer, List<Integer>>(); Map<Integer, List<Integer>> obstaclesEachY = new HashMap<Integer, List<Integer>>(); for (int[] obstacle : obstacles) { int obstacleX = obstacle[0], obstacleY = obstacle[1]; List<Integer> obstaclesX = obstaclesEachX.getOrDefault(obstacleX, new ArrayList<Integer>()); obstaclesX.add(obstacleY); obstaclesEachX.put(obstacleX, obstaclesX); List<Integer> obstaclesY = obstaclesEachY.getOrDefault(obstacleY, new ArrayList<Integer>()); obstaclesY.add(obstacleX); obstaclesEachY.put(obstacleY, obstaclesY); } int positionX = 0, positionY = 0; int maxDistance = 0; int length = commands.length; for (int i = 0; i < length; i++) { int command = commands[i]; if (command < 0) { if (command == -1) directionIndex = directionIndex == 3 ? 0 : directionIndex + 1; else if (command == -2) directionIndex = directionIndex == 0 ? 3 : directionIndex - 1; } else { int[] direction = directions[directionIndex]; if (directionIndex % 2 == 0) { List<Integer> obstaclesList = obstaclesEachX.getOrDefault(positionX, new ArrayList<Integer>()); for (int j = 1; j <= command; j++) { int nextY = positionY + direction[1]; if (obstaclesList.contains(nextY)) break; else { positionY = nextY; maxDistance = Math.max(maxDistance, positionX * positionX + positionY * positionY); } } } else { List<Integer> obstaclesList = obstaclesEachY.getOrDefault(positionY, new ArrayList<Integer>()); for (int j = 1; j <= command; j++) { int nextX = positionX + direction[0]; if (obstaclesList.contains(nextX)) break; else { positionX = nextX; maxDistance = Math.max(maxDistance, positionX * positionX + positionY * positionY); } } } } } return maxDistance; } } ############ class Solution { public int robotSim(int[] commands, int[][] obstacles) { int[][] dirs = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; Set<String> s = new HashSet<>(); for (int[] v : obstacles) { s.add(v[0] + "." + v[1]); } int ans = 0, p = 1; int x = 0, y = 0; for (int v : commands) { if (v == -2) { p = (p + 3) % 4; } else if (v == -1) { p = (p + 1) % 4; } else { while (v-- > 0) { int nx = x + dirs[p][0], ny = y + dirs[p][1]; if (s.contains(nx + "." + ny)) { break; } x = nx; y = ny; ans = Math.max(ans, x * x + y * y); } } } return ans; } } -
// OJ: https://leetcode.com/problems/walking-robot-simulation/ // Time: O(C) // Space: O(O) class Solution { private: long long hash(int x, int y) { return (long long)(x + 30000) * 100000 + y + 30000; } public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { unordered_set<long long> obs; for (auto &ob : obstacles) obs.insert(hash(ob[0], ob[1])); int ans = 0, x = 0, y = 0, dir = 0; // 0=N, 1=W, 2=S, 3=E int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} }; for (int cmd : commands) { if (cmd == -2) { dir = (dir + 1) % 4; } else if (cmd == -1) { dir = (dir + 3) % 4; } else { auto &d = dirs[dir]; while (cmd--) { if (obs.find(hash(x + d[0], y + d[1])) != obs.end()) break; x += d[0]; y += d[1]; ans = max(ans, x * x + y * y); } } } return ans; } }; -
class Solution: def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int: dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]] s = {(x, y) for x, y in obstacles} ans, p = 0, 1 x = y = 0 for v in commands: if v == -2: p = (p + 3) % 4 elif v == -1: p = (p + 1) % 4 else: for _ in range(v): nx, ny = x + dirs[p][0], y + dirs[p][1] if (nx, ny) in s: break x, y = nx, ny ans = max(ans, x * x + y * y) return ans ############ class Solution(object): def robotSim(self, commands, obstacles): """ :type commands: List[int] :type obstacles: List[List[int]] :rtype: int """ # directions = ['N', 'E', 'S', 'W'] # 0 - N, 1 - E, 2 - S, 3 - W position_offset = [(0, 1), (1, 0), (0, -1), (-1, 0)] obstacles = set(map(tuple, obstacles)) x, y, direction, max_distance = 0, 0, 0, 0 for command in commands: if command == -2: direction = (direction - 1) % 4 elif command == -1: direction = (direction + 1) % 4 else: x_off, y_off = position_offset[direction] while command: if (x + x_off, y + y_off) not in obstacles: x += x_off y += y_off command -= 1 max_distance = max(max_distance, x**2 + y**2) print(x, y) return max_distance -
func robotSim(commands []int, obstacles [][]int) int { dirs := [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1} } s := map[string]bool{} for _, v := range obstacles { t := strconv.Itoa(v[0]) + "." + strconv.Itoa(v[1]) s[t] = true } ans, p := 0, 1 x, y := 0, 0 for _, v := range commands { if v == -2 { p = (p + 3) % 4 } else if v == -1 { p = (p + 1) % 4 } else { for i := 0; i < v; i++ { nx, ny := x+dirs[p][0], y+dirs[p][1] t := strconv.Itoa(nx) + "." + strconv.Itoa(ny) if s[t] { break } x, y = nx, ny ans = max(ans, x*x+y*y) } } } return ans } func max(a, b int) int { if a > b { return a } return b }