2069.模拟行走机器人II

目标

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 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"]

解释：
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 次。

思路

有一个 w x h 的网格图，左下格子的坐标为 (0, 0)，初始时机器人朝向东方，机器人可以根据指令沿着当前朝向移动指定的步数，如果下一步到达了网格边界，则逆时针旋转 90° 继续尝试。实现 Robot 类，可以执行移动，以及获取机器人当前的位置、朝向。

暴力解法是模拟走每一步，如果越界则转向，直到剩余步数为 0。但是由于 step 调用次数最大为 10^4，所走步数是 int 类型，模拟走每一步会超时。

注意到机器人只能沿着网格的最外层绕圈，对周长 (w - 1 + h - 1)* 2 取模，只需模拟最后一圈即可。有一个出错点是回到原点的朝向，初始时朝向东方，回到原点时，朝向南方，需要特殊处理。

代码

/**
 * @date 2026-04-07 8:57
 */
public class Robot2069 {

    static class Robot {

        int[][] grid;
        int[][] directions = new int[][]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
        String[] res = new String[]{"South", "East", "North", "West"};
        int d = 1;
        int m;
        int n;
        int[] pos;

        public Robot(int width, int height) {
            m = height;
            n = width;
            grid = new int[m][n];
            pos = new int[]{0, 0};
        }

        public void step(int num) {
            int step = num % (m + n + m + n - 4);
            // 当位于原点，方向朝东时，再走 k 圈的方向应该朝南，如果不在原点的话，方向还是朝东
            if (step == 0 && d == 1 && pos[0] == 0 && pos[1] == 0) {
                d = 0;
            }
            while (step > 0) {
                while (pos[0] + directions[d][0] < 0
                        || pos[0] + directions[d][0] == n
                        || pos[1] + directions[d][1] < 0
                        || pos[1] + directions[d][1] == m
                ) {
                    d = ++d % 4;
                }
                pos[0] += directions[d][0];
                pos[1] += directions[d][1];
                step--;
            }
        }

        public int[] getPos() {
            return pos;
        }

        public String getDir() {
            return res[d];
        }
    }

}
/**
 * Your Robot object will be instantiated and called as such:
 * Robot obj = new Robot(width, height);
 * obj.step(num);
 * int[] param_2 = obj.getPos();
 * String param_3 = obj.getDir();
 */

性能