RotatingBot

作者：高睿泉

关键字：模拟，讨论

题目简述

如果有一个$w \times h$的方形网格，在$(0,0)$中放一个机器人(开始朝东)，机器人按如下规则移动：

1.机器人不会到达一个格子两次或走出边界

2.每次移向它面对方向的相邻一格，如果不能移动，则机器人逆时针转$90^{\circ}$角，如果仍然不能移动，则结束整个移动过程

3.机器人可以被人工停止移动

现在给定每次机器人掉头前连续行走的格子数的序列$moves$,判断是否存在这样的网格，如果存在求出这个网格的最小面积。

数据范围

$|moves|,moves_{i}\leq 50$

算法一

由于数据范围较小，可以先模拟机器人行走的过程。根据以下几种情况讨论:

1.如果中途重复经过一个格子则不存在方案。

2.假设初始横纵坐标范围均为$[0,0]$,在每次行走结束后，如果下一步超过原来的范围，那么就可以更新边界，如果两次修改同一边界（比如横坐标的下界），则不存在方案。

3.如果没有达到边界，下一步的位置未经过，则不存在方案。

4.如果存在方案，由于最优情况下不存在未经过的行列，那么横纵坐标的上下界之差的乘积即为答案。

时间复杂度$O(\sum moves_{i})$