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

这是一道 「中等难度」 的题 

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

题目

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

• ：向左转 度
• ：向右转 度
• ：向前移动 个单位长度

在网格上有一些格子被视为障碍物 。第 i 个障碍物位于网格点 。

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

返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 ，则返回 ）

注意：

• 北表示 +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

提示：

• is one of the values in the list .
• 答案保证小于

题解思路

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

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

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

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

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

• 右转：加一，。
• 左转：减一，。因为可能为负，所以先加。
  
  

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

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

另外需要注意的一点是，如果每次判断是不是障碍物点都从 数组找一次的话，那么光查找障碍点的时间复杂度就已经是 了, 其中 为机器人行走的步数， 为障碍物的个数。

我们可以提前以的时间复杂度，将障碍物点初始化到一个哈希表当中，然后我们就可以用的时间复杂度来判断一个点是不是障碍物了，具体实现见代码。

代码实现

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
}

复杂度分析

• 时间复杂度：， 其中 为机器人行走的步数， 为障碍物的个数，为转换方向的次数。
• 空间复杂度：, 为障碍物的个数。

END