CF1506B Partial Replacement

给定一个数字 $k$ 和一个长度为 $n$ 的字符串 $s$，字符串只包含字符 '.' 和 '\*'。你需要将部分 '\*' 替换为 'x'，使得满足以下条件： - 原字符串中第一个 '\*' 必须被替换为 'x'； - 原字符串中最后一个 '\*' 必须被替换为 'x'； - 任意相邻两个被替换为 'x' 的字符之间的距离不能超过 $k$（更正式地说，如果你在位置 $i$ 和 $j$（$i < j$）处替换了字符，并且在 $[i+1, j-1]$ 区间内没有被替换为 'x' 的字符，则 $j-i$ 必须不超过 $k$）。 例如，如果 $n=7$，$s=$ .\*\*.\*\*\*，$k=3$，则以下字符串满足上述条件： - .xx.\*xx； - .x\*.x\*x； - .xx.xxx。 但例如，以下字符串不满足条件： - .\*\*.\*xx（第一个 '\*' 没有被替换为 'x'）； - .x\*.xx\*（最后一个 '\*' 没有被替换为 'x'）； - .x\*.\*xx（第 $2$ 和 $6$ 位置之间的距离大于 $k=3$）。 给定 $n$、$k$ 和 $s$，请你求出最少需要将多少个 '\*' 替换为 'x'，才能满足上述条件。

第一行包含一个整数 $t$（$1 \le t \le 500$）。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 50$）。 第二行包含一个长度为 $n$ 的字符串 $s$，只包含字符 '.' 和 '\*'。 保证字符串 $s$ 中至少有一个 '\*'。 保证任意相邻两个 '\*' 之间的距离不超过 $k$。

对于每组测试数据，输出一个整数，表示最少需要将多少个 '\*' 替换为 'x'，才能满足上述条件。

由 ChatGPT 4.1 翻译