5387: BZOJ1387：[Baltic2002]Moving Robots

在二维网格平面上有许多机器人在移动。每个机器人的状态由它所在的位置和面向的方位确定。每个机器人按照各自固定的指令执行移动。位置由一对整数(x, y)表示。机器人的方向有4个，用角度表示，分别是0，90，180，270。命令有两种，转身和移动。转身命令有一个参数D，是90，180或270，机器人当前的方向改变D个度数，C度将变为(C + D) mod 360。移动指令没有参数，机器人将按它的方向前进一个单位。0方向的移动，位置改变（1，0），方向90改变（0，1），方向180改变（-1，0），方向270改变（0，-1）。 一个机器人依次完成它自己的指令序列。序列执行完后机器人将停在最终的位置上。 两个机器人之间的行动不互相影响，同一个位置可以有多个机器人。 在机器人开始移动前，可以去掉一些指令，所以控制中心可以改变机器人的行动路线和最终位置。控制中心希望使所有的机器人最后到达同一个位置以进行检查。同时希望能够在去掉最少的指令情况下完成这个目标。 任务： 共有R(2 <= R <= 10)个机器人。每个机器人有它的初始位置，初始方向和命令序列。命令序列长度不超过50。计算需要去掉的最少的命令数

输入格式

Input data should be read from the file robots.in. The first line of the file contains integer R (2 ≤ R ≤ 10) – the number of robots. Then R sections of lines follow. Each section describes one robot. The first line of the section contains four integers, separated by single spaces: x, y – initial robot position (x, y), initial robot direction C (C = 0, 90, 180, or 270) and the length of robot’s command sequence n (1 ≤ n ≤ 50). Then the section contains n lines describing the sequence of commands, one command per line. The line of the step command contains single character S in the first position and the line of the turn command contains character T in the first position that is followed by turn parameter – integer D (D = 90, 180 or 270) and is separated by a single space

输出格式

需要去掉的最少的命令数

样例输入

2 
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 

样例输出

2

提示

There are 2 moving robots. The first robot has initial position (2, 0), direction 270 and a sequence of 5 commands. The second one has initial position (1, -1), direction 0 and a sequence of 8 commands. The minimum total number of commands to be removed that makes robots share final position is 2: for example, remove the 3-rd command of the first robot and the 5-th command of the second robot. The common final position in that case is (2, 1).

题目来源

没有写明来源