题目描述
这是 LeetCode 上的 2069. 模拟行走机器人 II ，难度为 中等。
Tag : 「模拟」、「脑筋急转弯」
给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0)(0,0)，右上角的格子为 (width - 1, height - 1)(width−1,height−1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人初始在格子 (0, 0)(0,0) ，方向为 "East"。
机器人可以根据指令移动指定的步数。每一步，它可以执行以下操作。
- 沿着当前方向尝试往前一步 。
- 如果机器人下一步将到达的格子超出了边界，机器人会逆时针转 90 度，然后再尝试往前一步。
如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。
请你实现 Robot 类：
Robot(int width, int height)初始化一个width x height的网格图，机器人初始在 (0, 0)(0,0)，方向朝"East"。void move(int num)给机器人下达前进num步的指令。int[] getPos()返回机器人当前所处的格子位置，用一个长度为 22 的数组 [x, y][x,y] 表示。String getDir()返回当前机器人的朝向，为"North"，"East"，"South"或者"West"。
示例 1：
输入： ["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "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.move(2); // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。 robot.move(2); // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。 robot.getPos(); // 返回 [4, 0] robot.getDir(); // 返回 "East" robot.move(2); // 朝东移动 1 步到达 (5, 0) ，并朝东。 // 下一步继续往东移动将出界，所以逆时针转变方向朝北。 // 然后，往北移动 1 步到达 (5, 1) ，并朝北。 robot.move(1); // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。 robot.move(4); // 下一步继续往北移动将出界，所以逆时针转变方向朝西。 // 然后，移动 4 步到 (1, 2) ，并朝西。 robot.getPos(); // 返回 [1, 2] robot.getDir(); // 返回 "West" 复制代码
提示：
- 2 <= width, height <= 1002<=width,height<=100
- 1 <= num <= 10^51<=num<=105
move，getPos和getDir总共调用次数不超过 10^4104 次。
模拟
根据题目给定的移动规则可知，机器人总是在外圈移动（共上下左右四条），而移动方向分为四类：
当行走步数为 mod = 2 * (w - 1) + 2 * (h - 1)mod=2∗(w−1)+2∗(h−1) 的整数倍时，会回到起始位置，因此我们可以通过维护一个变量 loc 来记录行走的总步数，并且每次将 loc 对 mod 进行取模来得到有效步数。
在回答 getPos 和 getDir 询问时，根据当前 loc 进行分情况讨论（见注释）。
另外还有一个小细节：根据题意，如果当前处于 (0, 0)(0,0) 位置，并且没有移动过，方向为 East，若移动过，方向则为 South，这可以通过一个变量 moved 来进行特判处理。
代码：
class Robot { String[] ss = new String[]{"East", "North", "West", "South"}; int w, h, loc; // loc: 有效（取模后）移动步数 boolean moved; // 记录是否经过移动，用于特判 (0,0) 的方向 public Robot(int width, int height) { w = width; h = height; } public void step(int num) { moved = true; loc += num; loc %= 2 * (w - 1) + 2 * (h - 1); } public int[] getPos() { int[] info = move(); return new int[]{info[0], info[1]}; } public String getDir() { int[] info = move(); int x = info[0], y = info[1], dir = info[2]; // 特殊处理当前在 (0,0) 的情况，当未移动过方向为 East，移动过方向为 South if (x == 0 && y == 0) return moved ? ss[3] : ss[0]; return ss[dir]; } int[] move() { if (loc <= w - 1) { // 当移动步数范围在 [0,w-1] 时，所在位置为外圈的下方，方向为 East return new int[]{loc, 0, 0}; } else if (loc <= (w - 1) + (h - 1)) { // 当移动步数范围在 [w,(w-1)+(h-1)] 时，所在位置为外圈的右方，方向为 North return new int[]{w - 1, loc - (w - 1), 1}; } else if (loc <= 2 * (w - 1) + (h - 1)) { // 当移动步数范围在 [(w-1)+(h-1)+1,2*(w-1)+(h-1)] 时，所在位置为外圈的上方，方向为 West return new int[]{(w - 1) - (loc - ((w - 1) + (h - 1))), h - 1, 2}; } else { // 当移动步数范围在 [2*(w-1)+(h-1)+1,2*(w-1)+2*(h-1)] 时，所在位置为外圈的左方，方向为 South return new int[]{0, (h - 1) - (loc - (2 * (w - 1) + (h - 1))), 3}; } } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2069 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
