与T2相比稍复杂的模拟题。 首先此题很显然是模拟每次的走动，但是暴力检查柱子会TLE。我们首先注意到如果当前 x/yx/yx/y 方向没有柱子，那么这个方向的移动不会受到任何影响。这启示我们使用 x,yx,yx,y 方向上的两个map来记录柱子所在的行或列。 如果当前移动的方向有柱子，那我们可以把这个方向上的柱子全部提取出来。（这里可以用之前记录的map为有柱子的所有方向都创建一个序列）不难发现，如果是向 x/yx/yx/y 增加的方向移动，那么最远移动距离就是 x/yx/yx/y 的后继 −1-1−1。若反方向移动，则最远移动距离就是 x/yx/yx/y 的前驱 +1+1+1。 （名词解释）设指定数为 aaa，则： ·后继：一个序列中大于 aaa 的最小值。 ·前驱：一个序列中小于 aaa 的最大值。 若将要移动的位置比最远移动距离要远，那么机器人只能停在最远移动距离处。否则正常移动。 而求序列中指定数前驱或后继可以用平衡树，但是在不涉及排名的情况下，使用stl容器set更为简便。

暴力就不说了。 注意到每一次移动，只会在横坐标与纵坐标之间的一个修改，而且障碍的坐标不变。所以考虑统计每一个 xxx 坐标所对应的 yyy 坐标们，以及 yyy 坐标所对应的 xxx 坐标们。 由于值域巨大，使用 map\texttt{map}map 存储。 现在我们进行操作。如果我们碰不到障碍，直接修改坐标就好了；如果碰到障碍了，那么我们一定是碰到了第一个在路上的障碍。明显的二分。 随便调一下，然后就过了。 时间复杂度：O((n+m)log⁡2n)O((n+m) \log^2n)O((n+m)log2n) Code:

二分 首先，机器人仅能沿横坐标与纵坐标方向移动。基于这一特性，我们可以分别按横坐标和纵坐标，对柱子的信息进行存储。考虑到坐标数值可能较大，使用map进行存储较为合适。 对于横、纵坐标上每个可能出现的点，我们将其存入对应的数组。完成数据存储后，每次机器人移动时，通过二分查找的方法，就能判断机器人当前位置与目标位置之间是否存在柱子。 时间复杂度 (O((n+q)log⁡(n)(n + q )\log(n)(n+q)log(n))