给出一个 m*n 的迷宫地图,其中 # 表示墙,. 表示空地。保证迷宫是连通的,现在你来把其中 k 个空地变为墙,让剩下的空地仍然是连通的。
第一行:3 个数 m, n, k,中间用空格分隔(1 <= m, n <= 500,k < s),其中 s 为所有空地的数量,m 为行数、n 为列数。
后面 m 行:每行 n 个字符 # 或 .。
输出修改后的迷宫地图,把你要变成墙的地方输出为 X。
5 4 5 #... #.#. .#.. ...# .#.#
#XXX #X#. X#.. ..#. .#.#
先统计所有空地的数量 s,然后从任意一个空地开始 BFS(或 DFS),恰好访问 s-k 个空地,最后把未被访问到的空地全部改为 X。这样保留下来的空地一定是连通的。
本题有多解,采用特殊判题(SPJ):任意一组满足“恰好 k 个 X、原有 # 不变、剩余空地连通”的输出均判为正确。