P3522.第1题-任务导航
题目内容
工作室正在研发“任务导航”活动，需要你实现人物的自动任务寻路系统按指令执行路径并完成“任务点”功能，最终输出人物停止位置。在一个无限范围的网格图上，分布有 n 个两两位置不同的“任务点”，你的初始位置在 (0,0) ，面向南。记当前位置为 (x0,y0) ，则：
-
向东走一格，位置变为 (x0+1,y0);
-
向南走一格，位置变为 (x0,y0−1);
-
向西走一格，位置变为 (x0−1,y0);
-
向北走一格，位置变为 (x0,y0+1) 。
系统会生成一条长度为 m 的指令序列，并执行。指令序列由 F、T 与 S 三种操作组成：
-
F：向当前朝向移动一格，若落在任务点位置则完成该任务点；
-
T：顺时针旋转 90° ;
-
S：触发“跳跃“操作，按如下步骤执行：
- 若当前无未清理任务点，则忽略该指令;
- 在剩余任务点中，选取距离当前位置曼哈顿距离最小的点;若有多点，优先横坐标最小，再优先纵坐标最小;
- 记所选任务点到当前位置的曼哈顿距离为k，删除前剩余任务点数为 m1 ;
- 瞬移至该任务点并清除之;
- 跳过随后 min(k,m1) 条指令;若剩余指令不足，则执行完即停机。
输出系统执行完所有指令后所在的坐标。
【名词解释】
曼哈顿距离：在平面上，点 (x,y) 与 (x′,y′) 的曼哈顿距离定义为 ∣x−x′∣+∣y−y′∣ 。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤10) 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 n,m(1≤n≤103;1≤m≤103) ，表示任务点数、指令长度。
第二行输入一个长度为 m 、仅由字符 F、T、S 构成的字符串 s ，表示指令序列。
此后 n 行，第 i 行输入两个整数 xi,yi(−50≤xi,yi≤50)，表示第 i 个任务点的坐标。
除此之外，保证 n 个任务点两两位置不同。
输出描述
对于每组测试数据，新起一行，输出两个整数 x,y，代表系统执行完所有指令后所在的坐标。
样例1
输入
3
2 9
SFFFTFSFF
-2 0
-1 1
2 6
SFFFTF
-2 0
-1 1
2 3
SFF
-2 0
-1 1
输出
-2 1
-3 1
-2 0
说明
对于第一组测试数据，
-
操作一执行第一个指令 S ，选中距离最近的任务点 (−2,0) (距离 2 )，瞬移并完成，然后跳过接下来的两条指令;
-
操作二执行第四个指令 F ，向南移动一格，使系统移动至 (−2,−1) ；
-
操作三执行第五个指令 T ，面向西；
-
操作四执行第六个指令 F ，向西移动一格，使系统移动至 (−3,−1) 。
后两组样例都是样例一的子集。
