LeetCode 2069. 模拟行走机器人 II【分类讨论】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。。

memcpy0

150人浏览 · 2026-04-10 02:33:19

memcpy0 · 2026-04-10 02:33:19 发布

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (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：

example-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"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 **北** （不是朝西）。
robot.step(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

提示：

2 <= width, height <= 100
1 <= num <= 10^5
step ，getPos 和 getDir 总共调用次数不超过 10^4 次。

解法分类讨论， $O (1)$ 时间复杂度

下面将 $w i d t h$ 简称为 $w$ ，把 $h e i g h t$ 简称为 $h$ 。

根据题意，机器人只能在网格图的最外圈中移动，移动一整圈需要 $2 (w + h - 2)$ 步。

为什么只能在最外圈移动呢？很简单，机器人初始在 $(0, 0)$ ，方向向东，机器人无法自己改变方向，只能在越界时逆向转 $90\degree$ 才能改变方向，也就是说机器人必然在最外圈中移动！

设当前移动的总步数模 $2 (w + h - 2)$ 的结果为 $s$ 。分类讨论：

如果 $s < w$ ，机器人向右走了 $s$ 步，位于 $(s, 0)$ ，面朝东。
如果 $w\le s < w+h-1$ ，机器人先向右走 $w - 1$ 步，再往北走 $s - (w - 1)$ 步，位于 $(w - 1, s - w + 1)$ ，面朝北。
如果 $\le s < 2w+h-2$ ，机器人先向右走 $w - 1$ 步，再往北走 $h - 1$ 步，到达右上角 $(w - 1, h - 1)$ ，再往西走 $s - (w - 1) - (h - 1)$ 步，位于 $(w - 1 - (s - (w - 1) - (h - 1)), h - 1) = (2 w + h - s - 3, h - 1)$ ，面朝西。
否则，机器人先向右走 $w - 1$ 步，再往北走 $h - 1$ 步，再往西走 $w - 1$ 步，到达左上角 $(0, h - 1)$ ，再往南走 $s - 2 (w - 1) - (h - 1)$ 步，位于 $(0, h - 1 - (s - 2 (w - 1) - (h - 1))) = (0, 2 (w + h) - s - 4)$ ，面朝南。

注意：总步数为 $0$ 时，机器人面朝东，但总步数为 $2 (w + h - 2)$ 的正整数倍时，机器人面朝南。需要特判总步数为 $0$ 的特殊情况嘛？不需要，当总步数大于 $0$ 时，我们可把取模后的范围从 $[0, 2 (w + h - 2) - 1]$ 调整到 $[1, 2 (w + h - 2)]$ ，从而使原先模为 $0$ 的总步数变为 $2 (w + h - 2)$ ，落入面朝南的分支中，这样就可以避免特判了。

class Robot {
    private int w, h, s;

    public Robot(int width, int height) {
        w = width;
        h = height;
        s = 0;
    }

    public void step(int num) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        s = (s + num - 1) % ((w + h - 2) * 2) + 1;
    }

    public int[] getPos() {
        Object[] t = getState();
        return new int[]{(int) t[0], (int) t[1]};
    }

    public String getDir() {
        Object[] t = getState();
        return (String) t[2];
    }

    private Object[] getState() {
        if (s < w) {
            return new Object[]{s, 0, "East"};
        } else if (s < w + h - 1) {
            return new Object[]{w - 1, s - w + 1, "North"};
        } else if (s < w * 2 + h - 2) {
            return new Object[]{w * 2 + h - s - 3, h - 1, "West"};
        } else {
            return new Object[]{0, (w + h) * 2 - s - 4, "South"};
        }
    }
}

class Robot {
    int w;
    int h;
    int s = 0;

    tuple<int, int, string> getState() {
        if (s < w) {
            return {s, 0, "East"};
        } else if (s < w + h - 1) {
            return {w - 1, s - w + 1, "North"};
        } else if (s < w * 2 + h - 2) {
            return {w * 2 + h - s - 3, h - 1, "West"};
        } else {
            return {0, (w + h) * 2 - s - 4, "South"};
        }
    }

public:
    Robot(int width, int height) : w(width), h(height) {}

    void step(int num) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        s = (s + num - 1) % ((w + h - 2) * 2) + 1;
    }

    vector<int> getPos() {
        auto [x, y, _] = getState();
        return {x, y};
    }

    string getDir() {
        return get<2>(getState());
    }
};

class Robot:
    def __init__(self, width: int, height: int) -> None:
        self.w = width
        self.h = height
        self.s = 0

    def step(self, num: int) -> None:
        # 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        # 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        self.s = (self.s + num - 1) % ((self.w + self.h - 2) * 2) + 1

    def _getState(self) -> Tuple[int, int, str]:
        w, h, s = self.w, self.h, self.s
        if s < w:
            return s, 0, "East"
        if s < w + h - 1:
            return w - 1, s - w + 1, "North"
        if s < w * 2 + h - 2:
            return w * 2 + h - s - 3, h - 1, "West"
        return 0, (w + h) * 2 - s - 4, "South"

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

    def getDir(self) -> str:
        return self._getState()[2]

struct Robot {
    w: i32,
    h: i32,
    s: i32,
}

impl Robot {
    fn new(width: i32, height: i32) -> Self {
        Self { w: width, h: height, s: 0 }
    }

    fn step(&mut self, num: i32) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        self.s = (self.s + num - 1) % ((self.w + self.h - 2) * 2) + 1;
    }

    fn get_state(&self) -> (i32, i32, String) {
        let w = self.w;
        let h = self.h;
        let s = self.s;
        if s < w {
            (s, 0, "East".to_string())
        } else if s < w + h - 1 {
            (w - 1, s - w + 1, "North".to_string())
        } else if s < w * 2 + h - 2 {
            (w * 2 + h - s - 3, h - 1, "West".to_string())
        } else {
            (0, (w + h) * 2 - s - 4, "South".to_string())
        }
    }

    fn get_pos(&self) -> Vec<i32> {
        let (x, y, _) = self.get_state();
        vec![x, y]
    }

    fn get_dir(&self) -> String {
        let (_, _, d) = self.get_state();
        d
    }
}

type Robot struct {
	w, h, step int
}

func Constructor(width, height int) Robot {
	return Robot{width, height, 0}
}

func (r *Robot) Step(num int) {
	// 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
	// 把 step 取模调整到 [1, (w+h-2)*2]，这样不需要特判 step == 0 时的方向
	r.step = (r.step+num-1)%((r.w+r.h-2)*2) + 1
}

func (r *Robot) getState() (x, y int, dir string) {
	w, h, step := r.w, r.h, r.step
	switch {
	case step < w:
		return step, 0, "East"
	case step < w+h-1:
		return w - 1, step - w + 1, "North"
	case step < w*2+h-2:
		return w*2 + h - step - 3, h - 1, "West"
	default:
		return 0, (w+h)*2 - step - 4, "South"
	}
}

func (r *Robot) GetPos() []int {
	x, y, _ := r.getState()
	return []int{x, y}
}

func (r *Robot) GetDir() string {
	_, _, d := r.getState()
	return d
}

var Robot = function(width, height) {
    this.w = width;
    this.h = height;
    this.s = 0;
};

Robot.prototype.step = function(num) {
    // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
    // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s === 0 时的方向
    this.s = (this.s + num - 1) % ((this.w + this.h - 2) * 2) + 1;
};

Robot.prototype.getState = function() {
    const w = this.w, h = this.h, s = this.s;
    if (s < w) {
        return [s, 0, "East"];
    } else if (s < w + h - 1) {
        return [w - 1, s - w + 1, "North"];
    } else if (s < w * 2 + h - 2) {
        return [w * 2 + h - s - 3, h - 1, "West"];
    } else {
        return [0, (w + h) * 2 - s - 4, "South"];
    }
};

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

Robot.prototype.getDir = function() {
    return this.getState()[2];
};

typedef struct {
    int w;
    int h;
    int s;
} Robot;

Robot* robotCreate(int width, int height) {
    Robot* r = malloc(sizeof(Robot));
    r->w = width;
    r->h = height;
    r->s = 0;
    return r;
}

void robotStep(Robot* r, int num) {
    // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
    // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
    r->s = (r->s + num - 1) % ((r->w + r->h - 2) * 2) + 1;
}

int* robotGetPos(Robot* r, int* returnSize) {
    int w = r->w, h = r->h, s = r->s;
    int x, y;
    if (s < w) {
        x = s;
        y = 0;
    } else if (s < w + h - 1) {
        x = w - 1;
        y = s - w + 1;
    } else if (s < w * 2 + h - 2) {
        x = w * 2 + h - s - 3;
        y = h - 1;
    } else {
        x = 0;
        y = (w + h) * 2 - s - 4;
    }

    int* ans = malloc(2 * sizeof(int));
    *returnSize = 2;
    ans[0] = x;
    ans[1] = y;
    return ans;
}

char* robotGetDir(Robot* r) {
    int w = r->w, h = r->h, s = r->s;
    if (s < w) {
        return "East";
    } else if (s < w + h - 1) {
        return "North";
    } else if (s < w * 2 + h - 2) {
        return "West";
    } else {
        return "South";
    }
}

void robotFree(Robot* r) {
    free(r);
}