题目描述

一个机器人在网格中的(0, 0)位置，它会收到下面三种指令：

1. -2：表示向左转
2. -1：表示向右转
3. 1 <= x <= 9：表示前进x步

网格中会有障碍物，输入的obstacle数组第i个元素表示(obstacle[i][0], obstacle[i][1])有障碍物，机器人遇到障碍物便无法前进，只能停在障碍物前一个网格等待下一个指令。

返回机器人在移动过程中离出发点最远的距离的平方。

样例

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
说明: 机器人会遇到在(2, 4)的障碍物， 因此会在左转前停在(1, 4)处，之后再左转前进4步到(1, 8)处。

注意

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31.

算法

按照题目要求移动即可。用direction记录机器人移动的方向（正向/负向），用axis记录机器人是在x还是y方向上移动，另外移动时需要判断是否遇到障碍物。为了迅速判断机器人在移动时是否遇到障碍物，可以将机器人所在位置(x, y)进行encode，表示为x*100000+y，这样所有的位置都会对应一个编码，放到set中，对每一个位置去查询是否在set中，这样$O(1)$复杂度便可以判断是否遇到障碍物。

时间复杂度分析：每一个指令都是$O(1)$复杂度，因此复杂度为O(n)，n为max{commands.length, obstacles.length}。

C++ 代码

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<long> obset;
        for(int i = 0;i<obstacles.size();i++){
            int x = obstacles[i][0];
            int y = obstacles[i][1];
            long obpos = x*100000+y;
            obset.insert(obpos);
        }
        int direction=1;//1表示正向 -1表示负向
        int axis=1;//0表示x轴 1表示y轴
        int posx = 0;
        int posy = 0;
        int res = 0;
        for(int i = 0;i<commands.size();i++){
            if(commands[i]==-1){
                if(axis==0)
                    direction*=-1;
                axis = (axis+1)%2;
            }
            else if (commands[i]==-2){
                if(axis==1)
                    direction*=-1;
                axis = (axis+1)%2;
            }
            else if(commands[i]>0){
                if(axis==0){//x
                    while(commands[i]--){
                        posx += direction;
                        long pos = posx*100000+posy;
                        if(obset.find(pos)!=obset.end()){
                            posx -= direction;
                            break;
                        }
                    }
                }
                if(axis==1){
                    while(commands[i]--){
                        posy += direction;
                        long pos = posx*100000+posy;
                        if(obset.find(pos)!=obset.end()){
                            posy -= direction;
                            break;
                        }
                    }
                }
                int dist = posx*posx+posy*posy;//每一次前进后都判断是否需要更新结果
                if(dist>res)
                    res=dist;
            }

        }
        return res;
    }
};