2069-模拟行走机器人 II(Walking Robot Simulation II)

原文链接: https://leetcode-cn.com/problems/walking-robot-simulation-ii

英文原文

A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width - 1, height - 1). The grid is aligned with the four cardinal directions ("North", "East", "South", and "West"). A robot is initially at cell (0, 0) facing direction "East".

The robot can be instructed to move for a specific number of steps. For each step, it does the following.

Attempts to move forward one cell in the direction it is facing.
If the cell the robot is moving to is out of bounds, the robot instead turns 90 degrees counterclockwise and retries the step.

After the robot finishes moving the number of steps required, it stops and awaits the next instruction.

Implement the Robot class:

Robot(int width, int height) Initializes the width x height grid with the robot at (0, 0) facing "East".
void step(int num) Instructs the robot to move forward num steps.
int[] getPos() Returns the current cell the robot is at, as an array of length 2, [x, y].
String getDir() Returns the current direction of the robot, "North", "East", "South", or "West".

Example 1:

Input
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
Output
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

Explanation
Robot robot = new Robot(6, 3); // Initialize the grid and the robot at (0, 0) facing East.
robot.move(2);  // It moves two steps East to (2, 0), and faces East.
robot.move(2);  // It moves two steps East to (4, 0), and faces East.
robot.getPos(); // return [4, 0]
robot.getDir(); // return "East"
robot.move(2);  // It moves one step East to (5, 0), and faces East.
                // Moving the next step East would be out of bounds, so it turns and faces North.
                // Then, it moves one step North to (5, 1), and faces North.
robot.move(1);  // It moves one step North to (5, 2), and faces North (not West).
robot.move(4);  // Moving the next step North would be out of bounds, so it turns and faces West.
                // Then, it moves four steps West to (1, 2), and faces West.
robot.getPos(); // return [1, 2]
robot.getDir(); // return "West"

Constraints:

2 <= width, height <= 100
1 <= num <= 10⁵
At most 10⁴ calls in total will be made to step, getPos, and getDir.

中文题目

给你一个在 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 move(int num) 给机器人下达前进 num 步的指令。
int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [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 <= 100
1 <= num <= 10⁵
move ，getPos 和 getDir 总共调用次数不超过 10⁴ 次。

通过代码

高赞题解

分析

题目：
- 5911. 模拟行走机器人 II
思路：
- 直接按照题意模拟一遍。
- 我们发现机器人只会绕着网格图的外圈走，因此可以先将多余的圈数去掉，直接取余。
- 140/142测试点过不去，有两类错误：
  - 第一种，没有考虑到余数为0的时候，方向可能没有转过来，还是之前的方向。比如饶了一圈回到(0,0)，最开始是向右，但是此时正确答案应该向下。
  - 第二种，考虑了余数为0，但是直接对方向回退。在有的数据上，并不能直接回退方向，这个方向是固定的，可以写死。

代码

class Robot {
public:
    int w, h;
    int x, y, d;
    string dir[4] = {"East", "North", "West", "South"};
    int dx[4]={1, 0, -1, 0};
    int dy[4]={0, 1, 0, -1};
    Robot(int width, int height) {
        w = width;
        h = height;
        x = 0, y = 0, d = 0;
    }
    
    void move(int num) {
        // 外一圈的步数，这里不等于周长，而是长宽减一后的周长，最好手动模拟走一下。
        // 也可以这样写 int cc = 2*(w-1 + h-1);
        int cc = 2*w + 2*h - 4;
        num %= cc;
        // 140/142没考虑到的测试点 num == 0
        if(!num && !x && !y) d = 3;
        while(num--) {
            int nx = dx[d] + x, ny = dy[d] + y;
            if(nx < 0 || nx >= w || ny < 0 || ny >= h) {
                // 如果越界了，就逆时针转90度，换到下一个方向继续走
                d++, d %= 4;
                nx = dx[d] + x, ny = dy[d] + y;
            }
            x = nx, y = ny;
        }
    }
    
    vector<int> getPos() {
        return  {x, y};
    }
    
    string getDir() {
        return dir[d];
    }
};

/**
 * Your Robot object will be instantiated and called as such:
 * Robot* obj = new Robot(width, height);
 * obj->move(num);
 * vector<int> param_2 = obj->getPos();
 * string param_3 = obj->getDir();
 */

统计信息

通过次数	提交次数	AC比率
2213	11908	18.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途