A32397.TNT接力

"In the chaos of collapsing blocks and deadly traps, survival isn't just about speed, but knowing where to land next."

在你和队友探索 Minecraft 的试炼房时，你们遇到了一群 Bogged 骷髅。听起来很恐怖，对吗？这种稀有的骷髅变种可以在一次攻击中给你施加剧毒。大家一时惊慌失措，开始四处逃跑，而试炼房中充满了各种复杂的谜题，最著名的是 $\mathtt{TNT}$ 桥，每次踩到方块，方块就会塌陷。你的小队中有多少人能够逃脱并生还呢？

---

给定一个由 $N$ 个方块组成的序列 $S_1, S_2, ..., S_N$，它们组成了玩家需要穿越的路线。每个方块要么是 $\mathtt{TNT}$ 方块，要么是空气方块。所有玩家都从位于 $S_1$ 前方的一个未显示的方块开始，目标是跳到 $S_N$ 之后的另一个未显示的方块完成路线。

玩家可以从左向右移动，也可以跳跃，每次最多跳过 $K$ 个方块。玩家可以踩在 $\mathtt{TNT}$ 方块上，但会掉落穿过空气方块。当一个玩家踩到 $\mathtt{TNT}$ 方块时，方块会塌陷并在原地留下空气方块。

找到最多有多少名玩家 $P$ 能够成功通过 $\mathtt{TNT}$ 桥并逃离试炼房，如果有无限名玩家能够完成这条路径，则输出 $-1$。

Problem Credits: Macw07。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $N$ 和 $K$，分别表示路径中的方块数和玩家可以跳跃的最大距离。

• 第二行包含一个长度为 $N$ 的字符串 $S_1, S_2, ..., S_N$，表示路径上的方块类型。每个方块可以是以下之一：

  • $\mathtt{TNT}$ 方块，记作 #
  • 空气方块，记作 -

对于每组测试数据，输出一个整数 $P$，表示最多能成功通过 $\mathtt{TNT}$ 路径的玩家人数。如果有无限多的玩家能通过，则输出 $-1$。

数据范围与约定：

对于 $100\%$ 的数据，满足：

• $1 \leq T \leq 100$
• $1 \leq N \leq 10000$
• $1 \leq K \leq 10000$

样例解释：

对于第一个测试用例，做多可以让 $3$ 位玩家参与这个跑酷。一个可行的方案如下：

1. 在第一位玩家跑完后，局面可以用 -##--- 表示。
2. 在第二位玩家跑完后，局面可以用 -#---- 表示。
3. 在第三位玩家跑完后，局面可以用 ------ 表示。

可以发现在跑完三位玩家之后，第四位玩家无论如何也无法到达终点了，因此本测试用例的答案为 $3$。