【算法题解】24. 模拟机器人行走

Dear 丶 2024-03-23 11:21 44阅读 0赞

> 这是一道 **中等难度** 的题
> 
> [https://leetcode.cn/problems/walking-robot-simulation/description/][https_leetcode.cn_problems_walking-robot-simulation_description]

### 题目 ###

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

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

在网格上有一些格子被视为障碍物 `obstacles` 。第 `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 < = c o m m a n d s . l e n g t h < = 1 0 4 1 <= commands.length <= 10^4 1<=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 < = o b s t a c l e s . l e n g t h < = 1 0 4 0 <= obstacles.length <= 10^4 0<=obstacles.length<=104
 *   − 3 ∗ 104 < = x i , y i < = 3 ∗ 1 0 4 -3 \* 104 <= xi, yi <= 3 \* 10^4 −3∗104<=xi,yi<=3∗104
 *  答案保证小于  2 31 2^\{31\} 231

### 题解思路 ###

这道题理解起来其实很简单，就是求机器人走过的点位当中离原点 ( 0 ， 0 ) (0，0) (0，0)最远的点 ( x ， y ) (x，y) (x，y)，并计算其欧式距离的平方。

**具体实现逻辑为：** 循环遍历命令行数组 `commands`：

1.  如果遇到 `-2` 和 `-1` 就切换机器人方向。
2.  如果遇到 `1 <= x(前进步数) <= 9`按照当前方向一步一步前进。
    
     *  如果将要前进到的位置`（x, y）`在给定的障碍物 `obstacles` 数组中，就停下不能走了，也就是直接退出然后执行下一个命令`command`。
     *  否则每走一步，就计算一下 `ans = Math.max(ans, x2 + y2)`。

**示例2 图示**：

![7dce658c8397c8b13954ace8ce5310df.png][]

代码实现的难点在于方向的切换，这一类题目我们统一采用 **方向数组** 来处理。

我们定义当前方向为`dir`，可取值为 **\{0，1，2，3\}** ；分别代表 **\{北，东，南，西\}** 。见上图。

那么当机器人遇到改变方向的命令时，我们直接修改dir的值即可：

右转：加一，dir = (dir + 1) % 4。

左转：减一，dir = (dir - 1 + 4) % 4。因为dir - 1可能为负，所以先加4。

然后再分别在`x` 和 `y` 两个方向上定义两个方向数组，以Java为例：

int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

1.  方向为北（0）时：每次前进 x 不变，y 加一。
2.  方向为东（1）时：每次前进 x 加一，y 不变。
3.  方向为南（2）时：每次前进 x 不变，y 减一。
4.  方向为西（3）时：每次前进 x 减一，y 不变。

当遇到行走命令时，每前进一步，其位置变换就应该是`（x + dx[dir], y + dy[dir]）`。

另外需要注意的一点是，如果每次判断 ( x , y ) (x, y) (x,y)是不是障碍物点都从  o b s t a c l e s obstacles obstacles 数组找一次的话，那么光查找障碍点的时间复杂度就已经是  O ( m n ) O(mn) O(mn)了, 其中  m m m 为机器人行走的步数， n n n 为障碍物的个数。我们可以提前以 O ( n ) O(n) O(n)的时间复杂度，将障碍物点初始化到一个哈希表当中，然后我们就可以 O ( 1 ) O(1) O(1)的时间复杂度来判断一个点是不是障碍物了，具体实现见代码。

### 代码实现 ###

#### Java代码实现 ####

class Solution {
        
    
        private Set<Integer> obstacleSet = new HashSet<>();
        private int factor = 100000;
    
        public int robotSim(int[] commands, int[][] obstacles) {
        
    
            genObstacleSet(obstacles);
    
            // 当前方向，北：0， 东：1，南：2， 西：3
            int dir = 0;
    
            // 方向数组
            int[] dx = {
        0, 1, 0, -1};
            int[] dy = {
        1, 0, -1, 0};
    
            // 机器人位置
            int x = 0, y = 0; 
            int ans = 0;
            for(int command : commands){
        
                if(command == -2){
        
                    dir = (dir + 3) % 4;
                    continue;
                }if(command == -1){
        
                    dir = (dir + 1) % 4;
                    continue;
                }
                for(int i = 0; i < command; i++){
        
                    // 如果遇到障碍物，停止在当前位置
                    if(isObstacle(x + dx[dir], y + dy[dir])){
        
                        break;
                    }
                    x += dx[dir];
                    y += dy[dir];
                    ans = Math.max(ans, x * x + y * y);
                }
            }
    
            return ans;
    
        }
    
        // 判断是否是障碍物
        private boolean isObstacle(int x, int y){
        
            return obstacleSet.contains(factor * x + y);
        }
    
        private void genObstacleSet(int[][] obstacles){
        
    
            for(int[] obstacle : obstacles){
        
                obstacleSet.add(factor * obstacle[0] + obstacle[1]);
            }
    
        }
    }

#### Go代码实现 ####

func robotSim(commands []int, obstacles [][]int) int {
        
    
        // 初始化障碍点位
        obstacleMap := make(map[[2]int]bool)
        for _, obstacle := range obstacles {
        
            obstacleMap[[2]int{
        obstacle[0], obstacle[1]}] = true
        }
    
        // 当前方向
        dir := 0
    
        // 方向数组
        dx, dy := []int{
        0, 1, 0, -1}, []int{
        1, 0, -1, 0}
    
        // 当前位置
        x, y := 0, 0
    
        // 答案
        ans := 0
    
        for _, command := range commands {
        
            if command == -2 {
        
                dir = (dir + 3) % 4
                continue
            }
    
            if command == -1 {
        
                dir = (dir + 1) % 4
                continue
            }
    
            for i := 0; i < command; i++ {
        
                // 遇到障碍物
                if _, ok := obstacleMap[[2]int{
        x + dx[dir], y + dy[dir]}]; ok {
        
                    break;
                }
                x += dx[dir]
                y += dy[dir]
    
                ans = max(ans, x * x + y * y)
            }
        }
    
        return ans
    
    }
    
    func max(a int, b int) int {
        
        if a > b {
        
            return a
        }
        return b
    }

### 复杂度分析 ###

*  时间复杂度： O ( m + n + k ) O(m + n + k) O(m\+n\+k)， 其中  m m m 为机器人行走的步数， n n n 为障碍物的个数， k k k为转换方向的次数。
 *  空间复杂度： O ( n ) O(n) O(n),  n n n 为障碍物的个数。

[https_leetcode.cn_problems_walking-robot-simulation_description]: https://leetcode.cn/problems/walking-robot-simulation/description/
[7dce658c8397c8b13954ace8ce5310df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3be114136fe14c4baca7a14f9af7867a.png