斯坦福炒虾机器人爆火，能做满汉全席还会切菜洗碗叠被子。

最近斯坦福炒虾机器人在网上爆火，这款机器人会做饭，洗碗，擦桌子，叠被子，收拾衣服等各种功能，真的是太酷了，我们来看下，第一个是机器人在炒虾。

机器人在洗碗：

机器人在擦桌子：

还可以自己乘坐电梯：

还会做各种菜：

‍

还可以做家务，收拾衣服，叠被子等。

详细内容大家可以到网站：https://mobile-aloha.github.io/ 观看视频，因为视频在公众号上传需要审核，我把视频转gif图了，但公众号对图片的大小也都有限制，所以这里对gif图进行了大量的压缩，看起来播放会很快。

机器人这么智能，必须是经过大量运算才做出的动作，所以它肯定离不开算法，下面我们就来看一道和机器人有关的算法题，这题是LeetCode的第874题：模拟行走机器人。

问题描述

来源：LeetCode第874题

难度：中等

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

-2 ：向左转 90 度

-1 ：向右转 90 度

1 <= x <= 9 ：向前移动 x 个单位长度

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

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）

注意：

1，北方表示 +Y 方向。

2，东方表示 +X 方向。

3，南方表示 -Y 方向。

4，西方表示 -X 方向。

5，原点 [0,0] 可能会有障碍物。

示例1：

输入：commands = [4,-1,3], obstacles = []

输出：25

解释：

机器人开始位于 (0, 0)：

1. 向北移动 4 个单位，到达 (0, 4)

2. 右转

3. 向东移动 3 个单位，到达 (3, 4)

距离原点最远的是 (3, 4) ，距离为 3^2 + 4^2 = 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) ，距离为 1^2 + 8^2 = 65

• 1 <= commands.length <= 10^4

• commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。

• 0 <= obstacles.length <= 10^4

• -3 * 10^4 <= xi, yi <= 3 * 10^4

• 答案保证小于 2^31

问题分析

这题是让计算机器人所走的最远距离，我们直接模拟就行了，如果是负数只需要旋转方向即可，不要行走，-1就往右转，-2就往左转。

如果是正整数就往前走，这里要注意走的时候如果遇到障碍物就要停下了不要在走了，为了方便判断是否有障碍物，在JAVA和C++代码中我们把障碍物的坐标转成一维数组，存放到集合set中。

二维坐标 (i, j) 转一维，常见的方式是 (i*n+j)，这道题中 x, y 最大范围是 60000（-30000到30000），我们可以取n为60001，代码如下。

JAVA：

public int robotSim(int[] commands, int[][] obstacles) {
    // 题中的要求：北+Y，东+X，南-Y，西-X。
    // 方向坐标，分别表示往北，东，南，西4个方向。
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    Set<Integer> set = new HashSet<>();// 障碍物坐标，二维转一维。
    // 二维数组转一维数组存放到set中，为了方便查找。
    for (int[] obstacle : obstacles)
        set.add(obstacle[0] * 60001 + obstacle[1]);
    int x = 0;// 当前坐标
    int y = 0;// 当前坐标
    int direct = 0;// 当前方向，刚开始面向北方，0是北，1是东，2是南，3是西。
    int res = 0;// 记录行走到原点的最大距离。
    for (int command : commands) {
        if (command < 0) {// 改变行走方向。
            // -1往右，否则往左。
            direct += command == -1 ? 1 : -1;
            direct = (direct + 4) % 4;// 方向只能是0,1,2,3，不能越界。
        } else {// 往当前方向行走。
            // 慢慢一步一步走，遇到障碍物就停下，command表示行走的距离。
            for (int i = 0; i < command; i++) {
                // 遇到障碍物，停止。
                if (set.contains((x + dirs[direct][0]) * 60001 + y + dirs[direct][1]))
                    break;
                // 一步一步的走。
                x += dirs[direct][0];
                y += dirs[direct][1];
            }
            // 计算到原点的距离，保存最大值。
            res = Math.max(res, x * x + y * y);
        }
    }
    return res;
}

C++：

public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // 题中的要求：北+Y，东+X，南-Y，西-X。
        // 方向坐标，分别表示往北，东，南，西4个方向。
        int dirs[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        unordered_set<int> mySet;// 障碍物坐标，二维转一维。
        // 二维数组转一维数组存放到set中，为了方便查找。
        for (auto &obstacle : obstacles)
        mySet.emplace(obstacle[0] * 60001 + obstacle[1]);
        int x = 0;// 当前坐标
        int y = 0;// 当前坐标
        int direct = 0;// 当前方向，刚开始面向北方，0是北，1是东，2是南，3是西。
        int res = 0;// 记录行走到原点的最大距离。
        for (int command : commands) {
            if (command < 0) {// 改变行走方向。
                // -1往右，否则往左。
                direct += command == -1 ? 1 : -1;
                direct = (direct + 4) % 4;// 方向只能是0,1,2,3，不能越界。
            } else {// 往当前方向行走。
                // 慢慢一步一步走，遇到障碍物就停下，command表示行走的距离。
                for (int i = 0; i < command; i++) {
                    // 遇到障碍物，停止。
                    if (mySet.count((x + dirs[direct][0]) * 60001 + y + dirs[direct][1]))
                        break;
                    // 一步一步的走。
                    x += dirs[direct][0];
                    y += dirs[direct][1];
                }
                // 计算到原点的距离，保存最大值。
                res =max(res, x * x + y * y);
            }
        }
        return res;
    }

Python：

def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
    # 题中的要求：北+Y，东+X，南-Y，西-X。
    # 方向坐标，分别表示往北，东，南，西4个方向。
    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    mySet = set(map(tuple, obstacles))
    x, y = 0, 0  # 当前坐标
    direct = 0  # 当前方向，刚开始面向北方，0是北，1是东，2是南，3是西。
    res = 0  # 记录行走到原点的最大距离。
    for command in commands:
        if command < 0:  # -1  往右，否则往左。
            direct += 1 if command == -1 else -1
            direct = direct % 4;  # 方向只能是0, 1, 2, 3，不能越界。
        else:  # 慢慢一步一步走，遇到障碍物就停下，command表示行走的距离。
            for i in range(command):
                # 遇到障碍物，停止。
                if (x + dirs[direct][0], y + dirs[direct][1]) in mySet:
                    break;
                # 一步一步的走。
                x += dirs[direct][0];
                y += dirs[direct][1];
        # 计算到原点的距离，保存最大值。
        res = max(res, x * x + y * y);
    return res;

笔者简介

博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解700多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。

• 耗时两年终于出版了！

• 最近两个月，我公众号阅读从一千多增长到三四万，这样写才会出现爆款，才能被官方推荐。

• 华为今年的校招薪资，最高年薪90万。。。

• 2023年全球程序员薪酬报告出炉，北京年收入60多万排在亚洲第6。。。