LeetCode874. Walking Robot Simulation (模拟题）

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

• -2: turn left 90 degrees
• -1: turn right 90 degrees
• 1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

1. 0 <= commands.length <= 10000
2. 0 <= obstacles.length <= 10000
3. -30000 <= obstacle[i][0] <= 30000
4. -30000 <= obstacle[i][1] <= 30000
5. The answer is guaranteed to be less than 2 ^ 31.

解法
传统的模拟方法即可，把障碍物全都放到set里面，一步一步走。这样子即容易实现又不会出错。一开始的思路是判断当前点和下一点之间有没有障碍物，这种方法是错误的。

class Solution {
public:
    int robotSim(vector<int>& cmd, vector<vector<int>>& obs) {
        int dir[][2] = {{0,1},{1,0},{0,-1},{-1, 0}};
        int x=0,y=0;
	    int curdir = 0;
        int n = cmd.size(), m=obs.size();
        int ans = 0;
        set<pair<int,int>> block;
        for(int i=0;i < m ;i++) {
            block.insert({obs[i][0], obs[i][1]});
        }
        for(int i=0;i<n;i++) {
            if(cmd[i]==-1) {
                curdir = (curdir+1)%4;
            }
            else if(cmd[i]==-2) {
                curdir = (curdir+3)%4;
            }
            else{
                int step = cmd[i];
                int x1 =x , y1 = y;
                while(step--) {
                    x1 += dir[curdir][0],y1 += dir[curdir][1];
                    if (block.find({x1, y1}) != block.end())  {
                        break;
                    }
                    x=x1,y=y1;
                }
                ans = max(ans, x*x+y*y);
            }
	    }
        return ans;
    }
};