874. 模拟行走机器人

 874. 模拟行走机器人

描述：

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

-2：向左转90 度
-1：向右转 90 度
1 <= x <= 9：向前移动x个单位长度
在网格上有一些格子被视为障碍物。

第 i个障碍物位于网格点 ?(obstacles[i][0], obstacles[i][1])

如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从移动过程中原点到机器人的最大欧式距离的平方。

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)
示例2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处

提示：

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

解法1：112 ms    24.3 MB
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        //题目，是找移动过程中，到达原点的 最大欧式距离的平方
        //将数据 存入set，键值对中，方便判断
        //          0,1
        //           |
        //-1,0------0,0,-------1,0
        //           |
        //          0,-1
        //定义好移动的四个方向；可以使用取余的方法来判断，转向那个方向
        //(0,1)-->左转(-2)  --->x=（0+3）%4=3  ，dirx[3]=-1,
        //                  --->y=(1+3)%4=0,     diry[0]=1;
        //                  --->(x,y)=(-1,1);换方向了    
    //
        int dirx[4]={0,1,0,-1};
        int diry[4]={1,0,-1,0};
        //本想 用图，来做，但是，map<int,vector<int> > mp;这样麻烦，用set,unordered_set
        //unordered_set<pair<int,int>> st;
        set<pair<int,int> > st;//存储好，障碍点的坐标
        for(vector<int> &v:obstacles){
           st.insert({v[0],v[1]});
        }
        int x=0,y=0,dir=0,ans=0;
        for(int i=0;i<commands.size();i++){
            if(commands[i]==-2){//左转 90
                dir=(dir+3)%4;//原来方向+3 %4 为现在的方向  
            }else if(commands[i]==-1){//右转 90
                dir=(dir+1)%4;//原来方向+1 %4  为现在方向
            }else{//照着现在 方向遍历，移动位置
                for(int j=0;j<commands[i];j++){
                    int nextx=x+dirx[dir];//下一个 方向 位置坐标
                    int nexty=y+diry[dir];
                    if(st.find({nextx,nexty})!=st.end()){//去查是否是障碍物
                        //有，跳出这一轮的移动
                        break;
                    }//否则，每次都计算，太耗时间了 ，可以将ans拿出去
                    x=nextx;//没有找到障碍物，那么更新当前位置
                    y=nexty;
                    ans=max(ans,x*x+y*y);//同时计算 最大值
                }
            }
        }
        return ans;
    }
};

解法2：108 ms    24.4 MB    
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        //题目，是找移动过程中，到达原点的 最大欧式距离的平方
        //将数据 存入set，键值对中，方便判断
        //          0,1
        //           |
        //-1,0------0,0,-------1,0
        //           |
        //          0,-1
        //定义好移动的四个方向；可以使用取余的方法来判断，转向那个方向
        //(0,1)-->左转(-2)  --->x=（0+3）%4=3  ，dirx[3]=-1,
        //                  --->y=(1+3)%4=0,     diry[0]=1;
        //                  --->(x,y)=(-1,1);换方向了
        int dirx[4]={0,1,0,-1};
        int diry[4]={1,0,-1,0};
        //本想 用图，来做，但是，map<int,vector<int> > mp;这样麻烦，用set,unordered_set
        //unordered_set<pair<int,int>> st;
        set<pair<int,int> > st;//存储好，障碍点的坐标
        for(vector<int> &v:obstacles){
           st.insert({v[0],v[1]});
        }
        int x=0,y=0,dir=0,ans=0;
        for(int i=0;i<commands.size();i++){
            if(commands[i]==-2){//左转 90
                dir=(dir+3)%4;//原来方向+3 %4 为现在的方向
            }else if(commands[i]==-1){//右转 90
                dir=(dir+1)%4;//原来方向+1 %4  为现在方向
            }else{//照着现在 方向遍历，移动位置
                int nextx=x,nexty=y;
                for(int j=0;j<commands[i];j++){
                    nextx=x+dirx[dir];//下一个 方向 位置坐标
                    nexty=y+diry[dir];//这里的x,y,也要实时更新，
                    if(st.find({nextx,nexty})!=st.end()){//去查是否是障碍物
                        //是，跳出这一轮的移动
                        break;
                    }//否则，每次都计算，太耗时间了 
                       x=nextx;//没有找到障碍物，那么更新当前位置
                       y=nexty;
                }//线段L上距离一点A最远的点必是L的端点 ，所以，遇到障碍物，跳出，之前那个点，就是最远的距离，
                ans=max(ans,x*x+y*y);//同时计算 最大值
            }
        }
        return ans;
    }
};