解决方案


方法:情景模拟

思路

我们将一步步模拟机器人的路径。由于最多只有 90000 步,这足以通过给定的输入限制。

算法

我们将会存储机器人的位置和方向。如果机器人得到转弯的指令,我们就更新方向;否则就沿给定的方向走指定的步数。

必须注意使用 集合 Set 作为对障碍物使用的数据结构,以便我们可以有效地检查下一步是否受阻。如果不这样做,我们检查 该点是障碍点吗 可能会慢大约 10000 倍。

在某些语言中,我们需要将每个障碍物的坐标编码为 长整型 long 数据,以便它可以放入 集合 Set 数据结构中。或者,我们也可以将坐标编码为 字符串 string

复杂度分析

  • 时间复杂度:,其中 分别是 commandsobstacles 的长度。

  • 空间复杂度:,用于存储 obstacleSet 而使用的空间。