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
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>& o : obstacles)
      obstaclesSet.insert({o[0], o[1]});

    for (const int c : commands) {
      if (c == -1) {
        d = (d + 1) % 4;
      } else if (c == -2) {
        d = (d + 3) % 4;
      } else {
        for (int step = 0; step < c; ++step) {
          if (obstaclesSet.count({x + dirs[d], y + dirs[d + 1]}))
            break;
          x += dirs[d];
          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
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[] o : obstacles)
      obstaclesSet.add(new Pair<>(o[0], o[1]));

    for (final int c : commands) {
      if (c == -1) {
        d = (d + 1) % 4;
      } else if (c == -2) {
        d = (d + 3) % 4;
      } else {
        for (int step = 0; step < c; ++step) {
          if (obstaclesSet.contains(new Pair<>(x + dirs[d], y + dirs[d + 1])))
            break;
          x += dirs[d];
          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
24
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 c in commands:
      if c == -1:
        d = (d + 1) % 4
      elif c == -2:
        d = (d + 3) % 4
      else:
        for _ in range(c):
          if (x + dirs[d], y + dirs[d + 1]) in obstaclesSet:
            break
          x += dirs[d]
          y += dirs[d + 1]

      ans = max(ans, x * x + y * y)

    return ans