logo AlgoBeat OnlineJudge
登录 注册

#101387. [BZOJ 1387] [Baltic2002]Moving Robots

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

在二维网格平面上有许多机器人在移动。

每个机器人的状态由它所在的位置和面向的方位确定。

每个机器人按照各自固定的指令执行移动。

  • 位置由一对整数 表示。

  • 机器人的方向有 个,用角度表示,分别是

  • 命令有两种,转身和移动。

    • 转身命令有一个参数 ,是 之一,机器人当前的方向顺时针旋转 度,即 度将变为

    • 移动指令没有参数,机器人将按它的方向前进一个单位。

    • 方向的移动,

    • 方向的移动,

    • 方向的移动,

    • 方向的移动,

一个机器人依次完成它自己的指令序列。

序列执行完后机器人将停在最终的位置上。

两个机器人之间的行动不互相影响,同一个位置可以同时存在多个机器人。

在机器人开始移动前,可以去掉一些指令,所以控制中心可以改变机器人的行动路线和最终位置。

控制中心希望使所有的机器人最后到达同一个位置以进行检查。同时希望能够在去掉最少的指令情况下完成这个目标。

任务:共有 个机器人。每个机器人有它的初始位置,初始方向和命令序列。

计算需要去掉的最少的命令数。

输入格式

第一行一个整数 ,表示机器人的个数。

接下来 个部分描述每个机器人的信息。

每个部分的信息格式如下:

一行四个整数,,分别表示这个机器人的初始位置,初始方向和它的指令序列长度。

接下来 行,每行先读入一个字符 ,表示操作类型。

op='S',表示移动操作。

op='T',表示转身命令。再读入一个整数 ,表示转身命令的参数。

输出格式

需要去掉的最少的命令数。

样例

样例输入 #1

2 0 270 5 
S 
T 180 
S 
S 
S 
1 -1 0 8 
S 
S 
T 90 
S T 270 
S 
T 90 
S 

样例输出 #1

2

样例说明

删除第一个机器人的第三个操作和第二个机器人的第五个操作,能让两个机器人在 相遇。

数据范围与提示

对于 的数据,