← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6267 | Welcome24ever 和网格迷宫

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Welcome24ever 喜欢网格迷宫。一个网格迷宫是一个 $n \times m$ 的矩形迷宫，每个格子要么是空的“.”，要么是墙“#”。你只能在两个空的且有公共边的格子之间移动。

Welcome24ever 画了一个网格迷宫，其中所有空格子构成一个连通区域（也就是从任意一个空格子可以走到其他任意一个空格子）。他不喜欢墙太少，想把恰好 $k$ 个空格子改成墙，使得剩余空格子仍保持连通。请你帮助他做到这一点。

输入格式

  • 第一行：三个整数 $n,m,k$（$1 \le n,m \le 500$，$0 \le k s$），其中 $s$ 是原迷宫中空格子的数量。
  • 接下来 $n$ 行：每行 $m$ 个字符，组成原迷宫；“.” 表示空格子，“#” 表示墙。

输出格式

  • 输出 $n$ 行，表示更改后的迷宫；把将要变成墙的空格子标记为 “X”，其他格子保持原样（“.” 和 “#”）。
保证至少存在一种解；若有多种，输出任意一种即可。

输入输出样例

输入 #1
3 4 2
#..#
..#.
#...
输出 #1
#.X#
X.#.
#...
输入 #2
5 4 5
#...
#.#.
.#..
...#
.#.#
输出 #2
#XXX
#X#.
X#..
...#
.#.#
C++ 编辑器
输入
输出