RobotHerb
作者:吕欣
关键词:模拟,找规律
题意简述
某机器人在平面上原点处,它有一个长度为 n(≤50) 的命令序列,其中第 i 个命令中它会向当前方向移动 a[i] 个位置,然后顺时针旋转 a[i]×90 度,它会重复执行这个命令序列 T 次,求它最后停下来的位置和原点的曼哈顿距离。
约定:T,a[i]≤109,n≤50
算法分析
不难发现,无论机器人执行一次命令序列之后方向如何旋转,它重复执行 4 次命令序列之后总能回到原来的方向,所以每 4 次命令序列使它产生的位移是相同的。
我们暴力模拟 4 次命令序列,就能知道 4×⌊T4⌋ 次命令序列的执行使它产生的位移,同时它现在恢复了初始的朝向,我们对 的零散部分再模拟一遍即可得到它最终的的位置 ,答案即为 。
时间复杂度 ,空间复杂度