CF1254A Feeding Chicken

Long 是 Codeforces Fried Chicken（CFC）的超级粉丝。但由于 CFC 的价格不断上涨，他决定在自己的农场养鸡。 他的农场由一个 $r$ 行 $c$ 列的矩形网格组成。部分格子里有稻米，其他格子为空。农场里有 $k$ 只鸡。鸡的数量不超过农场中有稻米的格子数量。 Long 想要为每只鸡分配活动区域，即将农场的格子分配给这些鸡。他希望满足以下要求： - 农场的每个格子都恰好分配给一只鸡。 - 每只鸡至少分配到一个格子。 - 分配给每只鸡的格子集合必须连通。更具体地说，如果两个格子 $(x, y)$ 和 $(u, v)$ 分配给同一只鸡，这只鸡可以只经过属于自己的格子，并且每次只能移动到相邻（有公共边）的格子，从 $(x, y)$ 走到 $(u, v)$。 Long 还希望避免鸡为食物争斗。因此，他希望分配给每只鸡的稻米格子的最大数量与最小数量之差尽可能小。请你帮他完成分配。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $T$（$1 \le T \le 2 \cdot 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $r$、$c$ 和 $k$（$1 \leq r, c \leq 100, 1 \leq k \leq 62$），分别表示农场的行数、列数和鸡的数量。 接下来的 $r$ 行，每行包含 $c$ 个字符，每个字符为 "." 或 "R"，分别表示空格子或有稻米的格子。保证鸡的数量不超过农场中有稻米的格子数量。 保证所有测试用例中 $r \cdot c$ 的总和不超过 $2 \cdot 10^4$。

对于每个测试用例，输出 $r$ 行，每行 $c$ 个字符。每个字符应为小写英文字母、大写英文字母或数字。只有当两个格子分配给同一只鸡时，它们对应的字符才相同。大写字母和小写字母视为不同字符，因此 "A" 和 "a" 属于不同的鸡。 如果有多种最优方案，输出任意一种即可。

下图解释了样例输出。每种颜色代表一只鸡。带有图案（非纯色）的格子表示有稻米。 在第一个测试用例中，每只鸡分配到一个有稻米的格子，因此分配给鸡的稻米格子的最大值与最小值之差为 $0$。  在第二个测试用例中，有 $4$ 只鸡分配到 $3$ 个稻米格子，有 $2$ 只鸡分配到 $2$ 个稻米格子。因此最大值与最小值之差为 $3-2=1$。  在第三个测试用例中，每只鸡分配到 $3$ 个稻米格子。  在最后一个测试用例中，有 $62$ 只鸡，每只鸡分配到 $62$ 个稻米格子，因此每只鸡只能分配到一个格子。样例输出是其中一种可能的方案。 由 ChatGPT 4.1 翻译