Description

解放城市摆脱外星入侵者的战斗已经结束！人们为爱与和平的回归而欢欣鼓舞。

城市被表示为一个有 $R$ 行 $C$ 列的网格。网格上的某些格子是建筑物（无法看见、无法射击、无法行走），其余格子是街道（可以看见、可以射击、可以行走）。不幸的是，在战争期间，已经被击败的入侵者在城市中设置了自动安保炮台。这些炮台只会出现在街道上（不会在建筑物中）。它们对市民构成威胁，但幸运的是，街道上也有一些士兵（同样不会在建筑物中）。最初，没有任何士兵与炮台处于同一格子。

入侵者的炮台不会移动。它们体积很小，不会阻挡视线和射击。士兵无法穿过一个激活状态的炮台所在的格子，但炮台被摧毁后可以通过。炮台只能看到与自己处于同一行或同一列的士兵。如果士兵进入这样的格子，炮台不会开火；但如果士兵试图离开这样的格子（无论是进入后还是一开始就在该格子），炮台就会开火。幸运的是，士兵仍然可以在该格子射击，炮台不会因为射击而发现士兵的移动。这意味着你的士兵实际上不会阵亡，因为在最坏的情况下，他们总可以静止等待救援（也许会等很久）。或许你以后还有机会去救他们。

每个士兵最多可以进行 $M$ 次单位移动。每次移动只能向上下左右四个方向之一移动一个格子。士兵可以相互穿越，并且不会阻挡其他士兵或炮台的视线。每个士兵还有一颗子弹。如果士兵与某个炮台处于同一行或同一列，并且中间没有建筑物阻挡，则可以射击并摧毁该炮台。每次射击只能摧毁一个炮台，但士兵射击技术高超，即使有一个或多个炮台或士兵在射击路径上，也能击中更远处的炮台！

你将获得一张标记了士兵和炮台位置的地图。请问士兵们最多能摧毁多少个炮台？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个整数 $C$（地图宽度）、$R$（地图高度）和 $M$（每个士兵可移动的单位步数）。接下来的 $R$ 行每行包含 $C$ 个字符，. 表示街道，# 表示建筑物，S 表示士兵，T 表示炮台。

Output Format

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示最多可以被摧毁的炮台数量。接下来输出 $y$ 行，每行两个整数 $s_i$ 和 $t_i$，表示第 $i$ 个事件是编号为 $s_i$ 的士兵摧毁编号为 $t_i$ 的炮台（不需要具体说明士兵如何移动）。

士兵的编号从 1 开始，按照从上到下、每行从左到右的顺序编号。炮台的编号同理。

4
2 2 1
#S
T.
2 6 4
.T
.T
.T
S#
S#
S#
5 5 4
.....
SS#.T
SS#TT
SS#.T
.....
3 3 8
S.#
.#.
#.T

Case #1: 1
1 1
Case #2: 3
3 3
1 1
2 2
Case #3: 3
1 2
2 1
6 3
Case #4: 0

Hint

样例解释

在第 2 组样例中，一种可行的方案是让第 3 号士兵向上移动三格并射击第 3 号炮台。然后第 1 号士兵向上移动一格再向右移动一格（到达第 3 号炮台原本的位置），并穿过第 2 号炮台射击摧毁第 1 号炮台。最后第 2 号士兵向上移动三格并射击第 2 号炮台。

在第 3 组样例中，第 1 号士兵可以向上移动一格，然后向右移动三格并射击第 2 号炮台。第 2 号士兵可以向上移动一格，然后向右移动三格并射击第 1 号炮台。最后第 6 号士兵可以向下移动一格，然后向右移动三格并射击第 3 号炮台。其他士兵的移动步数不足以射击其他炮台。

在第 4 组样例中，士兵无法移动到与炮台同一行或同一列，因此无法摧毁炮台。

数据范围

• $1 \leq T \leq 100$。
• $0 \leq M < C \times R$。

小数据集（测试集 1 - 可见）

• 时间限制：7.5 秒。
• $1 \leq C \leq 30$。
• $1 \leq R \leq 30$。
• $S$ 的数量在 $1$ 到 $10$ 之间。
• $T$ 的数量在 $1$ 到 $10$ 之间。

大数据集（测试集 2 - 隐藏）

• 时间限制：15 秒。
• $1 \leq C \leq 100$。
• $1 \leq R \leq 100$。
• $S$ 的数量在 $1$ 到 $100$ 之间。
• $T$ 的数量在 $1$ 到 $100$ 之间。

由 ChatGPT 4.1 翻译