A6267. Welcome24ever 和网格迷宫
编程题
普及/提高-
知识点
题目描述
Welcome24ever 喜欢网格迷宫。一个网格迷宫是一个 $n \times m$ 的矩形迷宫，每个格子要么是空的“.”，要么是墙“#”。你只能在两个**空的**且**有公共边**的格子之间移动。
Welcome24ever 画了一个网格迷宫，其中**所有空格子构成一个连通区域**（也就是从任意一个空格子可以走到其他任意一个空格子）。他不喜欢墙太少，想把**恰好** $k$ 个空格子改成墙，使得**剩余空格子仍保持连通**。请你帮助他做到这一点。
Welcome24ever 画了一个网格迷宫，其中**所有空格子构成一个连通区域**（也就是从任意一个空格子可以走到其他任意一个空格子）。他不喜欢墙太少，想把**恰好** $k$ 个空格子改成墙，使得**剩余空格子仍保持连通**。请你帮助他做到这一点。
输入格式
- 第一行：三个整数 $n,m,k$（$1 \le n,m \le 500$，$0 \le k < s$），其中 $s$ 是原迷宫中空格子的数量。
- 接下来 $n$ 行：每行 $m$ 个字符，组成原迷宫；“.” 表示空格子，“#” 表示墙。
- 接下来 $n$ 行：每行 $m$ 个字符，组成原迷宫；“.” 表示空格子，“#” 表示墙。
输出格式
- 输出 $n$ 行，表示更改后的迷宫；把将要变成墙的空格子标记为 “X”，其他格子保持原样（“.” 和 “#”）。
保证至少存在一种解；若有多种，输出任意一种即可。
保证至少存在一种解；若有多种，输出任意一种即可。
输入输出样例
输入 #1
3 4 2 #..# ..#. #...
输出 #1
#.X# X.#. #...
输入 #2
5 4 5 #... #.#. .#.. ...# .#.#
输出 #2
#XXX #X#. X#.. ...# .#.#
说明/提示
## 样例解释
- 样例 1：把 2 个空格子改成 “X”，其余空格子仍相互连通。
- 样例 2：把 5 个空格子改成 “X”，其余空格子仍相互连通。
## 数据范围
- $1 \le n,m \le 500$，$0 \le k < s$（$s$ 为初始 “.” 总数）。
- 样例 1：把 2 个空格子改成 “X”，其余空格子仍相互连通。
- 样例 2：把 5 个空格子改成 “X”，其余空格子仍相互连通。
## 数据范围
- $1 \le n,m \le 500$，$0 \le k < s$（$s$ 为初始 “.” 总数）。