874.?模擬行走機(jī)器人

機(jī)器人在一個(gè)無(wú)限大小的 XY 網(wǎng)格平面上行走，從點(diǎn)?(0, 0)?處開(kāi)始出發(fā)，面向北方。該機(jī)器人可以接收以下三種類型的命令?commands?：

• -2?：向左轉(zhuǎn)?90?度
• -1?：向右轉(zhuǎn)?90?度
• 1 <= x <= 9?：向前移動(dòng)?x?個(gè)單位長(zhǎng)度

在網(wǎng)格上有一些格子被視為障礙物?obstacles?。第?i?個(gè)障礙物位于網(wǎng)格點(diǎn) ?obstacles[i] = (xi, yi)?。

機(jī)器人無(wú)法走到障礙物上，它將會(huì)停留在障礙物的前一個(gè)網(wǎng)格方塊上，但仍然可以繼續(xù)嘗試進(jìn)行該路線的其余部分。

返回從原點(diǎn)到機(jī)器人所有經(jīng)過(guò)的路徑點(diǎn)（坐標(biāo)為整數(shù)）的最大歐式距離的平方。（即，如果距離為?5?，則返回?25?）

注意：

• 北表示?+Y?方向。
• 東表示?+X?方向。
• 南表示?-Y?方向。
• 西表示?-X?方向。

示例 1：

輸入：commands = [4,-1,3], obstacles = []
輸出：25
解釋：
機(jī)器人開(kāi)始位于 (0, 0)：
1. 向北移動(dòng) 4 個(gè)單位，到達(dá) (0, 4)
2. 右轉(zhuǎn)
3. 向東移動(dòng) 3 個(gè)單位，到達(dá) (3, 4)
距離原點(diǎn)最遠(yuǎn)的是 (3, 4) ，距離為 32 + 42 = 25

示例?2：

輸入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
輸出：65
解釋：機(jī)器人開(kāi)始位于 (0, 0)：
1. 向北移動(dòng) 4 個(gè)單位，到達(dá) (0, 4)
2. 右轉(zhuǎn)
3. 向東移動(dòng) 1 個(gè)單位，然后被位于 (2, 4) 的障礙物阻擋，機(jī)器人停在 (1, 4)
4. 左轉(zhuǎn)
5. 向北走 4 個(gè)單位，到達(dá) (1, 8)
距離原點(diǎn)最遠(yuǎn)的是 (1, 8) ，距離為 12 + 82 = 65

提示：

• 1 <= commands.length <= 104
• commands[i]?的值可以取?-2、-1?或者是范圍?[1, 9]?內(nèi)的一個(gè)整數(shù)。
• 0 <= obstacles.length <= 104
• -3 * 104 <= xi, yi <= 3 * 104
• 答案保證小于?231

• class Solution {
  public:int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {//定義向北（0,1），向東（1,0），向南（0，-1），向西（-1,0）int px[4]={0,1,0,-1};int py[4]={1,0,-1,0};int n=commands.size();//記錄初始位置和方向int x=0,y=0,p=0,max1=0;//哈希表記錄障礙點(diǎn)，哈希表的每個(gè)空間表示障礙點(diǎn)的坐標(biāo)數(shù)字，set<pair<int,int>>ob;//二維數(shù)組轉(zhuǎn)成哈希表存查，方便后續(xù)的查找for(int i=0;i<obstacles.size();i++){ob.emplace(obstacles[i][0],obstacles[i][1]);}//遍歷每一次的動(dòng)作for(int i=0;i<n;i++){//如果左轉(zhuǎn)if(commands[i]==-2){p=(p+3)%4;}//右轉(zhuǎn)else if(commands[i]==-1){p=(p+1)%4;}//南北東西直行else{//每一個(gè)動(dòng)作都要按次移動(dòng)，for(int j=0;j<commands[i];j++){//計(jì)算橫向移動(dòng)int nx=x+px[p];int ny=y+py[p];//查找障礙點(diǎn)if(ob.count({nx,ny})){break;}x=nx;y=ny;max1=max(max1,x*x+y*y);}}}return max1;}
  };