【LeetCode】模拟行走机器人

题目描述：

机器人在一个无限大小的网格上行走，从点 (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)

解题思路：

用两个数组描述机器人向四个方向行走每一步的xy的变化值；每一步就查找这步走完后此处是否有障碍物，如有，则xy值不变，如没有，走出这一步。

这里最关键的点就是查找是否有障碍物存在，如果在vecor中查找将非常的慢，所以使用set集合容器。

代码：

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<pair<int, int>> obstacleSet;
        for(vector<int> obstacle: obstacles)
            obstacleSet.insert(make_pair(obstacle[0], obstacle[1]));
        int dx[4] = {0, 1, 0, -1};  
        int dy[4] = {1, 0, -1, 0};
        int dd = 0;
        int x=0, y=0, ans=0;
        for(int i=0; i<commands.size(); i++)
        {
            if(commands[i] == -1)
                dd = (dd+1)%4;
            else if(commands[i] == -2)
                dd = (dd+3)%4;
            else{
                for(int j=0; j<commands[i]; j++)
                {
                    int nx = x + dx[dd];
                    int ny = y + dy[dd];
                    if(obstacleSet.find(make_pair(nx, ny)) == obstacleSet.end())
                    {
                        x = nx;
                        y = ny;
                        ans = max(ans, x*x+y*y);
                    }
                    else
                        break;
                }
            }
        }
        return ans;
    }
};

补充：set集合容器的一般用法

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。

常见操作：
1、元素插入：insert()
2、中序遍历：用迭代器（类似vector）
3、反向遍历：利用反向迭代器reverse_iterator

set<int> s;
for(set<int>::reverse_iterator Iset = s.begin(); Iset!=s.end(); ++Iset) 

4、元素删除
s.erase(value);：删除值为value的元素
s.erase(iterator1, iterator2);：删除定位器[iterator1, iterator2)之间的元素
s.erase(iterator);：删除定位器指向的元素
5、元素检索：find()
若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。
if(obstacleSet.find(make_pair(nx, ny)) == obstacleSet.end())：表示没有找到该元素返回true。