Medium

题目描述

一个 width x height 的网格位于 XY 平面上，左下角的单元格位于 (0, 0)，右上角的单元格位于 (width - 1, height - 1)。网格与四个基本方向（“North”、“East”、“South” 和 “West”）对齐。机器人最初位于单元格 (0, 0) 面向 “East” 方向。

机器人可以接收指令移动特定数量的步数。对于每一步，它执行以下操作：

  • 尝试在其面向的方向上向前移动一个单元格。
  • 如果机器人要移动到的单元格超出边界，机器人会逆时针转动 90 度并重试该步骤。

机器人完成所需步数的移动后，它会停止并等待下一个指令。

实现 Robot 类：

  • Robot(int width, int height) 初始化 width x height 的网格，机器人位于 (0, 0) 面向 “East”。
  • void step(int num) 指示机器人向前移动 num 步。
  • int[] getPos() 返回机器人当前所在的单元格，作为长度为 2 的数组 [x, y]。
  • String getDir() 返回机器人当前的方向，“North”、“East”、“South” 或 “West”。

示例 1：

输入
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

约束条件：

  • 2 <= width, height <= 100
  • 1 <= num <= 10^5
  • 对 step、getPos 和 getDir 的总调用次数最多为 10^4 次。

解题思路

这道题的核心观察是机器人只能沿着网格的外围移动。当机器人撞到边界时，它会逆时针旋转90度。

主要思路：

  1. 模拟周长移动：机器人只能在网格的外围移动，我们可以将外围看作一个环形路径。外围的总长度是 2 * (width + height - 2)。

  2. 位置映射：将环形路径上的每个位置映射到实际的坐标和方向。我们可以按照顺时针顺序遍历外围：

    • 底边：从 (0,0) 到 (width-1, 0)，方向为 East
    • 右边：从 (width-1, 0) 到 (width-1, height-1)，方向为 North
    • 顶边：从 (width-1, height-1) 到 (0, height-1)，方向为 West
    • 左边：从 (0, height-1) 到 (0, 0)，方向为 South

  3. 优化计算：使用模运算来快速计算移动后的位置，避免逐步模拟。

  4. 特殊情况处理：初始状态下机器人在 (0,0) 面向 East，但如果机器人移动过至少一步后再次回到 (0,0)，它应该面向 South（因为它是从左边下来的）。

推荐解法：预计算外围每个位置对应的坐标和方向，然后使用模运算快速定位。

代码实现

class Robot {
private:
    int w, h;
    int perimeter;
    int pos;
    vector<pair<int, int>> coords;
    vector<string> dirs;
    bool moved;
    
public:
    Robot(int width, int height) {
        w = width;
        h = height;
        perimeter = 2 * (w + h - 2);
        pos = 0;
        moved = false;
        
        coords.resize(perimeter);
        dirs.resize(perimeter);
        
        int idx = 0;
        // Bottom edge: (0,0) to (w-1,0)
        for (int i = 0; i < w; i++) {
            coords[idx] = {i, 0};
            dirs[idx] = "East";
            idx++;
        }
        // Right edge: (w-1,1) to (w-1,h-1)
        for (int i = 1; i < h; i++) {
            coords[idx] = {w-1, i};
            dirs[idx] = "North";
            idx++;
        }
        // Top edge: (w-2,h-1) to (0,h-1)
        for (int i = w-2; i >= 0; i--) {
            coords[idx] = {i, h-1};
            dirs[idx] = "West";
            idx++;
        }
        // Left edge: (0,h-2) to (0,1)
        for (int i = h-2; i >= 1; i--) {
            coords[idx] = {0, i};
            dirs[idx] = "South";
            idx++;
        }
    }
    
    void step(int num) {
        moved = true;
        pos = (pos + num) % perimeter;
    }
    
    vector<int> getPos() {
        auto coord = coords[pos];
        return {coord.first, coord.second};
    }
    
    string getDir() {
        if (!moved && pos == 0) {
            return "East";
        }
        return dirs[pos];
    }
};

class Robot:
    def __init__(self, width: int, height: int):
        self.w = width
        self.h = height
        self.perimeter = 2 * (width + height - 2)
        self.pos = 0
        self.moved = False
        
        self.coords = []
        self.dirs = []
        
        # Bottom edge: (0,0) to (w-1,0)
        for i in range(width):
            self.coords.append((i, 0))
            self.dirs.append("East")
        
        # Right edge: (w-1,1) to (w-1,h-1)
        for i in range(1, height):
            self.coords.append((width-1, i))
            self.dirs.append("North")
        
        # Top edge: (w-2,h-1) to (0,h-1)
        for i in range(width-2, -1, -1):
            self.coords.append((i, height-1))
            self.dirs.append("West")
        
        # Left edge: (0,h-2) to (0,1)
        for i in range(height-2, 0, -1):
            self.coords.append((0, i))
            self.dirs.append("South")

    def step(self, num: int) -> None:
        self.moved = True
        self.pos = (self.pos + num) % self.perimeter

    def getPos(self) -> List[int]:
        x, y = self.coords[self.pos]
        return [x, y]

    def getDir(self) -> str:
        if not self.moved and self.pos == 0:
            return "East"
        return self.dirs[self.pos]

public class Robot {
    private int w, h, perimeter, pos;
    private bool moved;
    private List<(int, int)> coords;
    private List<string> dirs;

    public Robot(int width, int height) {
        w = width;
        h = height;
        perimeter = 2 * (w + h - 2);
        pos = 0;
        moved = false;
        
        coords = new List<(int, int)>();
        dirs = new List<string>();
        
        // Bottom edge: (0,0) to (w-1,0)
        for (int i = 0; i < w; i++) {
            coords.Add((i, 0));
            dirs.Add("East");
        }
        // Right edge: (w-1,1) to (w-1,h-1)
        for (int i = 1; i < h; i++) {
            coords.Add((w-1, i));
            dirs.Add("North");
        }
        // Top edge: (w-2,h-1) to (0,h-1)
        for (int i = w-2; i >= 0; i--) {
            coords.Add((i, h-1));
            dirs.Add("West");
        }
        // Left edge: (0,h-2) to (0,1)
        for (int i = h-2; i >= 1; i--) {
            coords.Add((0, i));
            dirs.Add("South");
        }
    }
    
    public void Step(int num) {
        moved = true;
        pos = (pos + num) % perimeter;
    }
    
    public int[] GetPos() {
        var coord = coords[pos];
        return new int[] {coord.Item1, coord.Item2};
    }
    
    public string GetDir() {
        if (!moved && pos == 0) {
            return "East";
        }
        return dirs[pos];
    }
}

var Robot = function(width, height) {
    this.width = width;
    this.height = height;
    this.x = 0;
    this.y = 0;
    this.dir = 0; // 0=East, 1=North, 2=West, 3=South
    this.perimeter = 2 * (width + height - 2);
    this.moved = false;
};

Robot.prototype.step = function(num) {
    if (this.perimeter === 0) return;
    
    num = num % this.perimeter;
    
    for (let i = 0; i < num; i++) {
        let nextX = this.x;
        let nextY = this.y;
        
        if (this.dir === 0) nextX++; // East
        else if (this.dir === 1) nextY++; // North
        else if (this.dir === 2) nextX--; // West
        else nextY--; // South
        
        if (nextX < 0 || nextX >= this.width || nextY < 0 || nextY >= this.height) {
            this.dir = (this.dir + 1) % 4;
            i--;
        } else {
            this.x = nextX;
            this.y = nextY;
            this.moved = true;
        }
    }
};

Robot.prototype.getPos = function() {
    return [this.x, this.y];
};

Robot.prototype.getDir = function() {
    if (!this.moved && this.x === 0 && this.y === 0) {
        return "South";
    }
    const dirs = ["East", "North", "West", "South"];
    return dirs[this.dir];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(width + height)O(width + height)
stepO(1)O(1)
getPosO(1)O(1)
getDirO(1)O(1)

说明：

  • 构造函数需要预计算外围的所有位置和对应方向，时间和空间复杂度都是 O(width + height)
  • 其他操作都是常数时间复杂度，通过模运算快速定位位置

相关题目