题目描述

背景

全新的方程式赛车团队 Irarref 需要你的帮助！Irarref 目前没有真正优秀的车手，但他们想要统治方程式赛车领域。由于公平对他们来说毫无意义，他们正在尝试开发一种几乎不需要车手干预的全自动驾驶控制系统。

在真正将自动驾驶控制系统用于赛道测试并冒着撞毁珍贵赛车的风险之前（他们对车手的安全并不太在意），他们希望在计算机模拟中进行测试。

问题

你需要模拟一辆赛车在给定赛道上的移动。为了简化问题，赛车只能在规则的二维网格的单元格中沿8个方向（水平、垂直和对角线）移动，方向编码如下：

7 0 1
6   2
5 4 3

每一回合，赛车执行以下命令之一：

无论执行哪种命令，赛车都会沿当前方向移动其速度值的单元格数，并经过其旧位置和新位置之间的所有单元格。当赛车加速或刹车时，其速度会在当前回合的移动之前调整。当赛车转向时，其方向会在移动之前改变。

赛道是一个二维规则网格，每个单元格可以是以下几种类型：

• 道路（用 "x" 表示）
• 非道路空间（但仍可行驶，用 "." 表示）
• 起点/终点线（也是道路，用 "s" 表示）
• 墙壁（用 "W" 表示）

每辆赛车的初始速度为0，并且有一个最大速度限制。当赛车撞到非道路空间时，其速度会在下一回合降至1，但当前回合的移动仍以当前速度完成。当赛车撞到墙壁时，赛车将立即撞毁，模拟停止，且不会有下一回合。

每辆赛车在赛道上都是独立的，因此不需要检查赛车之间的碰撞。

输入

第一行包含场景的数量。

对于每个场景：

• 第一行包含赛道的宽度 $w$ 和高度 $h$（$1 \leq w, h \leq 1000$）。
• 接下来的 $h$ 行包含赛道的布局，其中：
  • "x" 表示道路，
  • "." 表示非道路空间，
  • "s" 表示起点/终点线，
  • "W" 表示墙壁。
• 赛道区域的左上角坐标为 $(0, 0)$，右下角坐标为 $(w-1, h-1)$，坐标以 $(x, y)$ 形式给出，其中 $x$ 为水平方向，$y$ 为垂直方向。
• 接下来一行包含要模拟的赛车数量 $n$。
• 对于每辆赛车：
  • 第一行包含初始坐标 $(x, y)$、方向 $d$ 和最大速度 $m$，均为整数，用空格分隔，其中 $0 \leq x \leq w-1$，$0 \leq y \leq h-1$，$0 \leq d \leq 7$，$1 \leq m$。
  • 第二行包含一个字符串，其中每个字符代表一个命令，"m"、"a"、"b"、"l"、"r" 分别表示 move-on、accelerate、brake、left、right。每辆赛车的命令数量至少为1，最多为10000。

保证赛车的初始位置不在墙壁上，且赛车不会在不撞毁的情况下离开赛道区域。

输出

每个场景的输出以一行 "Scenario #i:" 开始，其中 $i$ 是从1开始的场景编号。对于每个场景，为每辆赛车输出以下信息：

• 如果赛车未撞毁，输出一行包含最终位置 $(x, y)$、方向和速度，用空格分隔。
• 如果赛车撞毁，输出一行包含撞毁点的坐标 $(x, y)$、撞毁时的方向和速度，以及单词 "crashed"，用空格分隔。
• 对于每次经过起点/终点线（即移动到起点/终点线单元格时），输出一行 "crossing startline:"，后跟空格、坐标 $(x, y)$、方向、速度和模拟的回合编号。这些行必须按照经过起点/终点线的顺序输出。

每个场景结束后输出一个空行。

示例输入

1
12 12
WWWWWWWWWWWW
W...xxxx...W
W..xxxxxx..W
W.xxWWWWxx.W
WxxWW..WWxxW
WxxW....WxxW
WssW....WxxW
WxxWW..WWxxW
W.xxWWWWxx.W
W..xxxxxx..W
W...xxxx...W
WWWWWWWWWWWW
2
1 6 0 3
armmrarrmrrrbrmmb
1 5 0 4
ararmrramrmar

示例输出

Scenario #1:
2 4 0 0
crossing startline: 2 6 0 1 13
5 11 5 2 crashed

来源

TUD Programming Contest 2004, Darmstadt, Germany