译自 ROI 2016 Day1 T2. Экспериментальная робототехника
鞑靼斯坦的各大学是教育机器人学领域的领先中心。为了推广这一方向,决定向中小学生提出一个有趣的实验——让机器人在有限空间内进行“生存实验”。
实验在一个大小为 的矩形场地上进行。在实验开始时,部分给定的格子中各放置一个尚未激活的机器人。在收到“开始”指令后,计时器启动,并在每秒开始时发出信号。在每次计时器信号发出后(但不超过 秒),允许激活部分机器人。
场地中的每个格子被涂成四种颜色之一,机器人通过传感器可以识别这些颜色。颜色对应于从当前格子移动到相邻格子的方向——北、南、东或西。在每次计时器信号发出的那一刻,所有已激活的机器人同时按照当前所在格子的颜色所指的方向移动到相邻格子。颜色的分布方式保证了:机器人永远不会移动出场地边界之外。
为了避免损坏,禁止以可能导致机器人碰撞的方式激活机器人。“碰撞”指的是两台或以上已激活的机器人在同一个时刻出现在同一个格子中。如果发生碰撞,则实验被视为失败。注意:若两个机器人从相邻格子相向移动,并最终互换位置,这不算作碰撞。
若所有已激活的机器人能在场地上无限长时间内持续移动而不发生碰撞,则实验视为成功完成。实验的结果定义为:被激活机器人的数量。
请你编写一个程序,帮助学生根据场地描述及初始放置的机器人位置,确定实验可能达到的最大结果;若有需要,还要指出应当激活哪些机器人以及在什么时刻激活,以达到这一最优结果。