【Leetcode】2069. Walking Robot Simulation II

题目地址：

https://leetcode.com/problems/walking-robot-simulation-ii/description/

给定一个$w\times h$的二维矩阵，一个机器人位于左下角$(0,0)$的位置，右上角的位置是$(w-1,h-1)$。这个机器人一开始方向向东，要求实现下面的操作：
1、以$w,h$初始化；
2、移动机器人$x$步，机器人除非走到边界之外，否则方向不变；如果走到边界之外，则走到边界的时候需要逆时针转向$90°$然后走剩余的步数；
3、返回机器人位置；
4、返回机器人朝向。

首先，机器人无论在哪儿，其走$x$步等价于走$x\mathrm{m}\mathrm{o}\mathrm{d}[(w+h-2)\ast 2]$步，所以可以先让$x$取模，取模完毕之后剩余步数暴力模拟即可。需要注意一个特殊情况，如果机器人从未走过，其朝向是东，但是一旦其走过，在其回到$(0,0)$的时候，朝向是南。其余的情况都可以直接模拟。代码如下：

class Robot {
 public:
  int X, Y, dir;
  string direction[4] = {"East", "North", "West", "South"};
  int x, y;
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};
  bool moved = false;

  Robot(int width, int height) {
    X = width;
    Y = height;
    x = y = dir = 0;
  }

  void step(int num) {
    moved = true;
    num %= (X - 1 + Y - 1) * 2;
    while (num) {
      int nx = x + dx[dir] * num, ny = y + dy[dir] * num;
      if (nx < 0 || nx >= X || ny < 0 || ny >= Y) {
        // 出界了，要转向
        dir = (dir + 1) % 4;
        if (nx < 0) num -= x, x = 0;
        else if (nx >= X) num -= X - 1 - x, x = X - 1;
        else if (ny < 0) num -= y, y = 0;
        else num -= Y - 1 - y, y = Y - 1;
      } else {
        // 没出界，则(nx, ny)即为新位置
        x = nx, y = ny;
        return;
      }
    }
  }

  vector<int> getPos() { return {x, y}; }

  string getDir() {
    // 如果走过，回到了原点，方向是南
    if (moved && !x && !y) return direction[3];
    return direction[dir];
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

所有操作时间复杂度$O(1)$，空间$O(1)$。