Skip to content

874. Walking Robot Simulation 👍

  • Time: $O(9 \cdot |\texttt{commands}| + |\texttt{obstacles}|) = O(|\texttt{commands}| + |\texttt{obstacles}|)$
  • Space: $O(|\texttt{obstacles}|)$
 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
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int ans = 0;
    int d = 0;  // 0 := north, 1 := east, 2 := south, 3 := west
    int x = 0;  // the start x
    int y = 0;  // the start y
    unordered_set<pair<int, int>, PairHash> obstaclesSet;

    for (const vector<int>& obstacle : obstacles) {
      const int x = obstacle[0];
      const int y = obstacle[1];
      obstaclesSet.insert({x, y});
    }

    for (const int command : commands) {
      if (command == -1) {
        d = (d + 1) % 4;
      } else if (command == -2) {
        d = (d + 3) % 4;
      } else {
        for (int step = 0; step < command; ++step) {
          if (obstaclesSet.contains({x + dirs[d][0], y + dirs[d][1]}))
            break;
          x += dirs[d][0];
          y += dirs[d][1];
        }
      }
      ans = max(ans, x * x + y * y);
    }

    return ans;
  }

 private:
  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};

 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
34
class Solution {
  public int robotSim(int[] commands, int[][] obstacles) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int ans = 0;
    int d = 0; // 0 := north, 1 := east, 2 := south, 3 := west
    int x = 0; // the start x
    int y = 0; // the start y
    Set<Pair<Integer, Integer>> obstaclesSet = new HashSet<>();

    for (int[] obstacle : obstacles) {
      final int x_ = obstacle[0];
      final int y_ = obstacle[1];
      obstaclesSet.add(new Pair<>(x_, y_));
    }

    for (final int command : commands) {
      if (command == -1) {
        d = (d + 1) % 4;
      } else if (command == -2) {
        d = (d + 3) % 4;
      } else {
        for (int step = 0; step < command; ++step) {
          if (obstaclesSet.contains(new Pair<>(x + dirs[d][0], y + dirs[d][1])))
            break;
          x += dirs[d][0];
          y += dirs[d][1];
        }
      }
      ans = Math.max(ans, x * x + y * y);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    ans = 0
    d = 0  # 0 := north, 1 := east, 2 := south, 3 := west
    x = 0  # the start x
    y = 0  # the start y
    obstaclesSet = {(x, y) for x, y in obstacles}

    for command in commands:
      if command == -1:
        d = (d + 1) % 4
      elif command == -2:
        d = (d + 3) % 4
      else:
        for _ in range(command):
          if (x + dirs[d][0], y + dirs[d][1]) in obstaclesSet:
            break
          x += dirs[d][0]
          y += dirs[d][1]
      ans = max(ans, x * x + y * y)

    return ans