LeetCode:874. 模拟行走机器人

本文已参与「新人创作礼」活动， 一同敞开创作之路。

874. 模拟行走机器人

来源：力扣（LeetCode）

链接: leetcode.cn/problems/wa…

机器人在一个无限巨细的 XY 网格平面上行走，从点 (0, 0) 处开端出发，面向北方。该机器人能够接纳以下三种类型的指令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为妨碍物 obstacles 。第 i 个妨碍物坐落网格点 obstacles[i]=(xi,yi)obstacles[i] = (x_i, y_i)obstacles[i]=(xi​,yi​) 。

机器人无法走到妨碍物上，它将会停留在妨碍物的前一个网格方块上，但仍然能够继续测验进行该路线的其余部分。

回来从原点到机器人一切通过的路径点（坐标为整数）的最大欧式间隔的平方。（即，如果间隔为 5 ，则回来 25 ）

留意：

• 北表明 +Y 方向。
• 东表明 +X 方向。
• 南表明 -Y 方向。
• 西表明 -X 方向。

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解说：
机器人开端坐落 (0, 0)：
1. 向北移动 4 个单位，抵达 (0, 4)
2. 右转
3. 向东移动 3 个单位，抵达 (3, 4)
间隔原点最远的是 (3, 4) ，间隔为 32 + 42 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解说：机器人开端坐落 (0, 0)：
1. 向北移动 4 个单位，抵达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被坐落 (2, 4) 的妨碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，抵达 (1, 8)
间隔原点最远的是 (1, 8) ，间隔为 12 + 82 = 65 

提示：

• 1<=commands.length<=1041 <= commands.length <= 10^41<=commands.length<=104
• commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
• 0<=obstacles.length<=1040 <= obstacles.length <= 10^40<=obstacles.length<=104
• −3∗104<=xi,yi<=3∗104-3 * 10^4 <= xi, yi <= 3 * 10^4−3∗104<=xi,yi<=3∗104
• 答案保证小于 2312^{31}231

解法

• 模拟+贪心算法： 模拟机器人走路，这儿需求留意方向
  • ( 0, 1) — 北：x不动，y向上一步
  • ( 1, 0) — 东：y不动，x向右一步
  • ( 0, -1) — 南：x不动，y向下一步
  • (-1, 0) — 西：y不动，x向左一步

顺时针方向，先确认方向，然后一步一步走，遇到妨碍就break，如果没有就更新坐标，核算间隔，更新最大间隔；妨碍能够运用哈希表，加快查询速度

代码实现

贪心算法

python实现

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        if not commands:
            return 0
        direntions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        cur_x, cur_y = 0, 0
        cur_dir = 0
        ans = 0
        obstacles = set(map(tuple, obstacles))
        for cmd in commands:
            if cmd == -1:
                cur_dir = (cur_dir+1) % 4
            elif cmd == -2:
                cur_dir = (cur_dir+3) % 4
            else:
                for i in range(cmd):
                    nx = cur_x + direntions[cur_dir][0]
                    ny = cur_y + direntions[cur_dir][1]
                    if (nx, ny) not in obstacles:
                        cur_x = nx
                        cur_y = ny
                        ans = max(ans, cur_x*cur_x+cur_y*cur_y)
                    else:
                        break
        return ans

c++实现

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        /*
            ( 0,  1)  -- 北：x不动，y向上一步
            ( 1,  0)  -- 东：y不动，x向右一步
            ( 0, -1)  -- 南：x不动，y向下一步
            (-1,  0)  -- 西：y不动，x向左一步
        */
        if (commands.size() == 0) return 0;
        int cur_x = 0, cur_y = 0, cur_dir = 0;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        unordered_map<int, unordered_set<int>> obs;
        for(auto& iter: obstacles) {
            obs[iter[0]].insert(iter[1]);
        }
        int ans = 0;
        for (auto &cmd : commands) {
            if (cmd == -1)
                cur_dir = (cur_dir+1) % 4;  // turn left
            else if (cmd == -2)
                cur_dir = (cur_dir+3) % 4;  // turn right
            else { // walk alone
                for (int i=0; i<cmd; i++) {
                    int nx = cur_x + directions[cur_dir].first;
                    int ny = cur_y + directions[cur_dir].second;
                    auto iter = obs.find(nx);
                    if (iter == obs.end() || iter->second.find(ny) == iter->second.end()) {
                        cur_x = nx;
                        cur_y = ny;
                        ans = max(ans, cur_x*cur_x+ cur_y*cur_y);
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时刻复杂度： $O(N+K)$ 其中 N, K 分别是 commands 和 obstacles 的长度。
• 空间复杂度： $O(K)$ 用于存储 obstacleSet 而运用的空间

参考

• leetcode.cn/problems/wa…