跳转至

2069. 模拟行走机器人 II

来源第 65 场双周赛 Q2难度中等分数1918

题目描述

给你一个在 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：

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 <= 105
  • step ，getPos 和 getDir 总共 调用次数不超过 104 次。

解法

方法一：分类讨论

思考

step 可达 \(10^5\) 且调用多次，逐步走格子会超时。机器人只沿矩形边界循环，周长 \(p=2(w+h-2)\)。位置对 \(p\) 取模后落在四条边上。

按累计步数分段还原坐标与朝向。未移动时朝东；回到原点且已移动过则朝南，与「刚走完最后一条边」一致。

我们记 \(mx = width - 1\) 和 \(my = height - 1\)，则机器人的运动轨迹是一个以 \((0, 0)\) 为左下角，而 \((mx, my)\) 为右上角的矩形的边界。我们可以将机器人的运动轨迹分为四段：

  1. 从 \((0, 0)\) 沿着 \(x\) 轴正方向运动到 \((mx, 0)\)，此时机器人的朝向为 "East"。
  2. 从 \((mx, 0)\) 沿着 \(y\) 轴正方向运动到 \((mx, my)\)，此时机器人的朝向为 "North"。
  3. 从 \((mx, my)\) 沿着 \(x\) 轴负方向运动到 \((0, my)\)，此时机器人的朝向为 "West"。
  4. 从 \((0, my)\) 沿着 \(y\) 轴负方向运动到 \((0, 0)\)，此时机器人的朝向为 "South"。

因此，我们可以将机器人的运动轨迹看作是一个长度为 \(p = 2 \cdot mx + 2 \cdot my\) 的循环。对于每次调用 step(num)，我们可以将机器人的当前位置加上 num，然后对 \(p\) 取模，得到机器人的新位置。根据机器人的新位置，我们可以判断出机器人的朝向和坐标。

注意，如果机器人没有移动过，那么它的朝向应该是 "East"。如果机器人移动过，且位置为 \((0, 0)\)，则机器人的朝向应该是 "South"。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

 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
class Robot:

    def __init__(self, width: int, height: int):
        self.mx = width - 1
        self.my = height - 1
        self.p = 2 * self.mx + 2 * self.my
        self.cur = 0
        self.moved = False

    def step(self, num: int) -> None:
        self.moved = True
        self.cur = (self.cur + num) % self.p

    def getPos(self) -> List[int]:
        d = self.cur
        mx, my = self.mx, self.my
        if 0 <= d <= mx:
            return [d, 0]
        if mx < d <= mx + my:
            return [mx, d - mx]
        if mx + my < d <= 2 * mx + my:
            return [mx - (d - (mx + my)), my]
        return [0, my - (d - (2 * mx + my))]

    def getDir(self) -> str:
        d = self.cur
        mx, my = self.mx, self.my
        if not self.moved:
            return "East"
        if 1 <= d <= mx:
            return "East"
        elif mx < d <= mx + my:
            return "North"
        elif mx + my < d <= 2 * mx + my:
            return "West"
        return "South"


# Your Robot object will be instantiated and called as such:
# obj = Robot(width, height)
# obj.step(num)
# param_2 = obj.getPos()
# param_3 = obj.getDir()

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Robot {

    private int mx, my, p, cur;
    private boolean moved;

    public Robot(int width, int height) {
        this.mx = width - 1;
        this.my = height - 1;
        this.p = 2 * this.mx + 2 * this.my;
        this.cur = 0;
        this.moved = false;
    }

    public void step(int num) {
        this.moved = true;
        this.cur = (this.cur + num) % this.p;
    }

    public int[] getPos() {
        int d = this.cur;
        int mx = this.mx, my = this.my;

        if (0 <= d && d <= mx) {
            return new int[] {d, 0};
        }
        if (mx < d && d <= mx + my) {
            return new int[] {mx, d - mx};
        }
        if (mx + my < d && d <= 2 * mx + my) {
            return new int[] {mx - (d - (mx + my)), my};
        }
        return new int[] {0, my - (d - (2 * mx + my))};
    }

    public String getDir() {
        int d = this.cur;
        int mx = this.mx, my = this.my;

        if (!this.moved) {
            return "East";
        }
        if (1 <= d && d <= mx) {
            return "East";
        } else if (mx < d && d <= mx + my) {
            return "North";
        } else if (mx + my < d && d <= 2 * mx + my) {
            return "West";
        }
        return "South";
    }
}

/**
 * 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();
 */

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Robot {
public:
    int mx, my, p, cur;
    bool moved;

    Robot(int width, int height) {
        mx = width - 1;
        my = height - 1;
        p = 2 * mx + 2 * my;
        cur = 0;
        moved = false;
    }

    void step(int num) {
        moved = true;
        cur = (cur + num) % p;
    }

    vector<int> getPos() {
        int d = cur;
        int mx = this->mx, my = this->my;

        if (0 <= d && d <= mx) {
            return {d, 0};
        }
        if (mx < d && d <= mx + my) {
            return {mx, d - mx};
        }
        if (mx + my < d && d <= 2 * mx + my) {
            return {mx - (d - (mx + my)), my};
        }
        return {0, my - (d - (2 * mx + my))};
    }

    string getDir() {
        int d = cur;
        int mx = this->mx, my = this->my;

        if (!moved) {
            return "East";
        }
        if (1 <= d && d <= mx) {
            return "East";
        } else if (mx < d && d <= mx + my) {
            return "North";
        } else if (mx + my < d && d <= 2 * mx + my) {
            return "West";
        }
        return "South";
    }
};

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

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
type Robot struct {
    mx, my, p, cur int
    moved          bool
}

func Constructor(width int, height int) Robot {
    mx := width - 1
    my := height - 1
    return Robot{
        mx:    mx,
        my:    my,
        p:     2*mx + 2*my,
        cur:   0,
        moved: false,
    }
}

func (this *Robot) Step(num int) {
    this.moved = true
    this.cur = (this.cur + num) % this.p
}

func (this *Robot) GetPos() []int {
    d := this.cur
    mx, my := this.mx, this.my

    if 0 <= d && d <= mx {
        return []int{d, 0}
    }
    if mx < d && d <= mx+my {
        return []int{mx, d - mx}
    }
    if mx+my < d && d <= 2*mx+my {
        return []int{mx - (d - (mx + my)), my}
    }
    return []int{0, my - (d - (2*mx + my))}
}

func (this *Robot) GetDir() string {
    d := this.cur
    mx, my := this.mx, this.my

    if !this.moved {
        return "East"
    }
    if 1 <= d && d <= mx {
        return "East"
    } else if mx < d && d <= mx+my {
        return "North"
    } else if mx+my < d && d <= 2*mx+my {
        return "West"
    }
    return "South"
}

/**
 * Your Robot object will be instantiated and called as such:
 * obj := Constructor(width, height);
 * obj.Step(num);
 * param_2 := obj.GetPos();
 * param_3 := obj.GetDir();
 */

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Robot {
    private mx: number;
    private my: number;
    private p: number;
    private cur: number;
    private moved: boolean;

    constructor(width: number, height: number) {
        this.mx = width - 1;
        this.my = height - 1;
        this.p = 2 * this.mx + 2 * this.my;
        this.cur = 0;
        this.moved = false;
    }

    step(num: number): void {
        this.moved = true;
        this.cur = (this.cur + num) % this.p;
    }

    getPos(): number[] {
        const d = this.cur;
        const mx = this.mx,
            my = this.my;

        if (0 <= d && d <= mx) {
            return [d, 0];
        }
        if (mx < d && d <= mx + my) {
            return [mx, d - mx];
        }
        if (mx + my < d && d <= 2 * mx + my) {
            return [mx - (d - (mx + my)), my];
        }
        return [0, my - (d - (2 * mx + my))];
    }

    getDir(): string {
        const d = this.cur;
        const mx = this.mx,
            my = this.my;

        if (!this.moved) {
            return 'East';
        }
        if (1 <= d && d <= mx) {
            return 'East';
        } else if (mx < d && d <= mx + my) {
            return 'North';
        } else if (mx + my < d && d <= 2 * mx + my) {
            return 'West';
        }
        return 'South';
    }
}

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

评论