思路与题解

• 问题抽象：在无限网格上，初始在 $(0,0)$、朝向“下”。给定指令序列长度为 $m$，其中包含三类操作：前进 $F$、右转 $T$、跳跃 $S$。网格上有 $n$ 个互不相同的任务点，落到其坐标即清除之。

• 朝向与移动：按顺时针顺序编码方向为 $[0,1,2,3]$ 对应 $[右,下,左,上]$。初始方向 $d=1$（下）。单位移动向量依次为 $(1,0),(0,-1),(-1,0),(0,1)$。

• 指令含义

  • F：将坐标 $(x,y)$ 变为 $(x+\Delta_x[d],y+\Delta_y[d])$，若命中任务点则清除。
  • T：令 $d \leftarrow (d+1)\bmod 4$。
  • S：

题目内容

工作室正在研发“任务导航”活动，需要你实现人物的自动任务寻路系统按指令执行路径并完成“任务点”功能，最终输出人物停止位置。在一个无限范围的网格图上，分布有 $n$ 个两两位置不同的“任务点”，你的初始位置在 $(0,0)$ ，面向南。记当前位置为 $(x_0,y_0)$ ，则：

• 向东走一格，位置变为 $(x_0+1,y_0)$;

• 向南走一格，位置变为 $(x_0,y_0-1)$;

• 向西走一格，位置变为 $(x_0 -1,y_0)$;

• 向北走一格，位置变为 $(x_0,y_0+ 1)$ 。

系统会生成一条长度为 $m$ 的指令序列，并执行。指令序列由 $F、T$ 与 $S$ 三种操作组成：

• F：向当前朝向移动一格，若落在任务点位置则完成该任务点；

• T：顺时针旋转 $90°$ ;

• S：触发“跳跃“操作，按如下步骤执行：

  • 若当前无未清理任务点，则忽略该指令;
  • 在剩余任务点中，选取距离当前位置曼哈顿距离最小的点;若有多点，优先横坐标最小，再优先纵坐标最小;
  • 记所选任务点到当前位置的曼哈顿距离为k，删除前剩余任务点数为 $m_1$ ;
  • 瞬移至该任务点并清除之;
  • 跳过随后 $min(k,m_1)$ 条指令;若剩余指令不足，则执行完即停机。

  输出系统执行完所有指令后所在的坐标。

  【名词解释】

  曼哈顿距离：在平面上，点 $(x,y)$ 与 $(x',y')$ 的曼哈顿距离定义为 $|x-x'|+|y-y'|$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤T≤ 10)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(1≤n≤10^3;1≤m≤10^3)$ ，表示任务点数、指令长度。

第二行输入一个长度为 $m$ 、仅由字符 $F、T、S$ 构成的字符串 $s$ ，表示指令序列。

此后 $n$ 行，第 $i$ 行输入两个整数 $x_i,y_i(-50≤x_i,y_i≤50)$，表示第 $i$ 个任务点的坐标。

除此之外，保证 $n$ 个任务点两两位置不同。

输出描述

对于每组测试数据，新起一行，输出两个整数 $x,y$，代表系统执行完所有指令后所在的坐标。

样例1

输入

3
29
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)$ 。

后两组样例都是样例一的子集。