leetcode: 874. 模拟行走机器人

874. 模拟行走机器人

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/walking-robot-simulation/

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

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

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 $obstacles[i]=(x_i,y_i)$ 。

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

返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 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<=10^4$
• commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
• $0<=obstacles.length<=10^4$
• $-3\ast 10^4<=xi,yi<=3\ast 10^4$
• 答案保证小于 $2^{31}$

解法

• 模拟+贪心算法： 模拟机器人走路，这里需要注意方向
  • ( 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 而使用的空间

参考

• https://leetcode.cn/problems/walking-robot-simulation/solution/tu-jie-mo-ni-xing-zou-ji-qi-ren-by-dekeshile/