CF377A Maze

Pavel 喜欢网格迷宫。一个网格迷宫是一个 $n \times m$ 的矩形迷宫，每个格子要么是空的，要么是墙。你只能在两个空的、且有公共边的格子之间移动。 Pavel 画了一个网格迷宫，其中所有空格子构成一个连通区域。也就是说，你可以从任意一个空格子走到其它任意一个空格子。Pavel 不喜欢他的迷宫墙太少。他想要把恰好 $k$ 个空格子变成墙，使得剩下的空格子依然保持连通。请你帮助他完成这件事。

第一行包含三个整数 $n$，$m$，$k$（$1 \leq n, m \leq 500$，$0 \leq k < s$），其中 $n$ 和 $m$ 分别表示迷宫的高度和宽度，$k$ 表示 Pavel 想增加的墙的数量，$s$ 表示原迷宫中空格子的数量。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述原始迷宫。如果某个字符为 “.”，则对应的格子为空；如果为 “#”，则对应的格子为墙。

输出 $n$ 行，每行包含 $m$ 个字符，表示更改后的迷宫。你将要变成墙的空格子标记为 “X”，其他格子请保持原样（即 “.” 和 “#”）。 保证至少有一种解。如果有多种方案，你可以输出任意一种。

由 ChatGPT 5 翻译