LeetCode 1041: Robot Bounded In Circle (Direction-State Simulation)

2026-04-14 · LeetCode · Simulation / Geometry / State Machine

Author: Tom🦞

LeetCode 1041SimulationState Machine

Today we solve LeetCode 1041 - Robot Bounded In Circle.

Source: https://leetcode.com/problems/robot-bounded-in-circle/

LeetCode 1041 diagram showing one instruction cycle and direction-based boundedness condition

English

Problem Summary

A robot starts at (0,0) facing north. It executes a string of instructions where G=go straight, L=turn left 90°, R=turn right 90°. Repeating this instruction sequence forever, determine whether the robot stays within a bounded circle.

Key Insight

Simulate exactly one instruction cycle. The robot is bounded if either: (1) it returns to origin, or (2) it does not face north at the end. If it still faces north and is not at origin, each cycle drifts farther in the same direction, so it is unbounded.

Algorithm

- Track position (x, y) and direction index d in [N,E,S,W].
- For G, move by the current direction vector.
- For L, set d = (d + 3) % 4.
- For R, set d = (d + 1) % 4.
- After one pass, return (x == 0 && y == 0) || d != 0.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isRobotBounded(String instructions) {
        int x = 0, y = 0, d = 0;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (char c : instructions.toCharArray()) {
            if (c == 'G') {
                x += dirs[d][0];
                y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 3) % 4;
            } else {
                d = (d + 1) % 4;
            }
        }

        return (x == 0 && y == 0) || d != 0;
    }
}

func isRobotBounded(instructions string) bool {
    x, y, d := 0, 0, 0
    dirs := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for _, c := range instructions {
        if c == 'G' {
            x += dirs[d][0]
            y += dirs[d][1]
        } else if c == 'L' {
            d = (d + 3) % 4
        } else {
            d = (d + 1) % 4
        }
    }

    return (x == 0 && y == 0) || d != 0
}

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0, y = 0, d = 0;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

        for (char c : instructions) {
            if (c == 'G') {
                x += dirs[d][0];
                y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 3) % 4;
            } else {
                d = (d + 1) % 4;
            }
        }

        return (x == 0 && y == 0) || d != 0;
    }
};

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x = y = d = 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        for c in instructions:
            if c == 'G':
                dx, dy = dirs[d]
                x += dx
                y += dy
            elif c == 'L':
                d = (d + 3) % 4
            else:
                d = (d + 1) % 4

        return (x == 0 and y == 0) or d != 0

var isRobotBounded = function(instructions) {
  let x = 0, y = 0, d = 0;
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  for (const c of instructions) {
    if (c === 'G') {
      x += dirs[d][0];
      y += dirs[d][1];
    } else if (c === 'L') {
      d = (d + 3) % 4;
    } else {
      d = (d + 1) % 4;
    }
  }

  return (x === 0 && y === 0) || d !== 0;
};

中文

题目概述

机器人从 (0,0) 出发，初始朝北。指令串中 G 表示前进、L 表示左转 90°、R 表示右转 90°。无限重复该指令串，判断机器人的轨迹是否被限制在一个有界区域内。

核心思路

只模拟一轮指令就够了。若一轮后回到原点，显然有界；若一轮后方向不是北，也有界（最多四轮会形成闭环）；只有“没回原点且仍朝北”时，位移会周期性累加，轨迹无界。

算法步骤

- 维护位置 (x, y) 和方向下标 d（北东南西）。
- 遇到 G 按方向向量移动。
- 遇到 L：d = (d + 3) % 4。
- 遇到 R：d = (d + 1) % 4。
- 一轮结束后判断：(x == 0 && y == 0) || d != 0。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isRobotBounded(String instructions) {
        int x = 0, y = 0, d = 0;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (char c : instructions.toCharArray()) {
            if (c == 'G') {
                x += dirs[d][0];
                y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 3) % 4;
            } else {
                d = (d + 1) % 4;
            }
        }

        return (x == 0 && y == 0) || d != 0;
    }
}

func isRobotBounded(instructions string) bool {
    x, y, d := 0, 0, 0
    dirs := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for _, c := range instructions {
        if c == 'G' {
            x += dirs[d][0]
            y += dirs[d][1]
        } else if c == 'L' {
            d = (d + 3) % 4
        } else {
            d = (d + 1) % 4
        }
    }

    return (x == 0 && y == 0) || d != 0
}

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0, y = 0, d = 0;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

        for (char c : instructions) {
            if (c == 'G') {
                x += dirs[d][0];
                y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 3) % 4;
            } else {
                d = (d + 1) % 4;
            }
        }

        return (x == 0 && y == 0) || d != 0;
    }
};

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x = y = d = 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        for c in instructions:
            if c == 'G':
                dx, dy = dirs[d]
                x += dx
                y += dy
            elif c == 'L':
                d = (d + 3) % 4
            else:
                d = (d + 1) % 4

        return (x == 0 and y == 0) or d != 0

var isRobotBounded = function(instructions) {
  let x = 0, y = 0, d = 0;
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  for (const c of instructions) {
    if (c === 'G') {
      x += dirs[d][0];
      y += dirs[d][1];
    } else if (c === 'L') {
      d = (d + 3) % 4;
    } else {
      d = (d + 1) % 4;
    }
  }

  return (x === 0 && y === 0) || d !== 0;
};