SP11906 ROT - Rescue On Time

在未来，有一个专门从邪恶组织手中解救人质的机构。这些邪恶组织躲在一个虽然声称是绝密但众人皆知的地堡里。我们的救援机构拥有一种特别的能力：能进行时间旅行。无论前往未来还是回到过去，均可随意次数使用。但每次只允许前进或后退一分钟，或停留当前时间，不能像跳跃那样跨越多分钟。例如，不可能一次性跳到三分钟后的未来或两分钟前的过去。这个机构每次只关注解救一个人质，因为那些“坏人”愚蠢到只能绑架一个人并藏起来（虽然他们的地堡很大）。 现在，我们需要编写一个程序，计算救援特工到达人质所需的最少时间步数（实际上是我太懒，所以这项工作交给你）。重要的是，人质在某个时间点之后会被“坏人”杀掉，所以特工绝不能超过这个时间。此外，在特定时间之前，人质还没有被关进地堡，因此回到那个时间点也是毫无意义的。特工可以向任意相邻的上下左右方向移动，但不能斜向移动。由于特工可以自由使用时间，所以等待原地也是不必要的。 地图符号说明如下： - ‘X’ 表示特工的起始位置，保证特工从时间点 1 开始。 - ‘#’ 表示墙壁，无法穿越。 - ‘s’ 表示空地，可以通行。 - ‘!’ 表示“坏人”的位置。 - ‘O’ 表示人质的位置，即目标。

第一行输入一个整数 $T$，表示测试用例的数量，$T \leq 10$。接下来的每组输入包含三个整数 $C, R, \text{Time}$，分别表示地图的列数、行数和时间限制，其中 $C \leq 15$，$R \leq 15$，$\text{Time} \leq 10$（每超过一单位时间，人质将处于危险中；而在时间 1 之前，人质尚未出现，因而无意义）。接下来的 $\text{Time}$ 行，每行包含一个 $R \times C$ 的矩阵，描述各时间点上警卫位置和新的空地情况（当然，墙壁和人质的位置是固定的）。

输出特工达到人质位置的最少时间步数。如果无法救援人质，输出「Hostage is death, destroy the bunker」。 **本翻译由 AI 自动生成**