← 返回题目列表

AtCoder · jag2017autumn_f

F. RPG 制作者

中文机器翻译题面 查看原题

问题陈述

您正计划创建 RPG 地图。该地图由大小为 $H \times W$ 的网格表示。该网格中的每个单元格要么是 @, *, #,或 .。符号的含义如下。

  • @:起始单元格。故事应该从这个牢房开始。
  • *:城市小区。故事就在这个牢房中经过或结束。
  • #:道路小区。
  • .:空单元格。

您已经在输入部分中描述的某些约束下找到了起始单元格和所有城市单元格,但尚未找到道路单元格。然后,您应该决定将哪些单元格设置为道路单元格。

在这里,你想要的“旅程”存在于这张地图上。因为你想删除故事的分支,所以旅程必须被取消。更正式地说,旅程是一个单元序列,并且必须满足以下条件:

  1. 旅程必须包含尽可能多的城市单元。
  2. 旅程必须由该地图中不同的非空单元格组成。
  3. 旅程必须从起始单元格开始。
  4. 旅程必须以城市单元格之一结束。
  5. 旅程必须包含所有道路单元格。也就是说,不包含在旅程中的道路单元一定不存在。
  6. 旅​​程必须分叉。更详细地说,除了旅程终点的单元之外,所有道路单元和城市单元都必须与其他两个单元共享边,这两个单元也都包含在旅程中。然后,每个起始单元格和旅程结束的单元格必须与旅程中包含的另一个单元格共享边。
  7. 旅途中您无需考虑游览城市的顺序。

最初,地图不包含道路单元。您可以将任何空单元格更改为道路单元格,以进行满足上述条件的旅程。您的任务是打印一张地图,最大限度地增加旅程中的城市数量。


输入

输入由以下形式的单个测试用例组成。

$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$

第一行由两个整数 $H$ 和 $W$ 组成。对于某些正整数 $n$ 和 $m$ ($1 \le n, m \le 10$),$H$ 和 $W$ 保证满足 $H = 4n - 1$ 和 $W = 4m - 1$。 以下 $H$ 线代表没有道路单元的地图。第 $(i+1)$ 行由长度为 $W$ 的字符串 $S_i$ 组成。 $S_i$ 的第 $j$ 个字符是 *, @ or . 如果 $i$ 和 $j$ 都是奇数,否则 .。出现次数 网格中的 @ 正好是一个。保证网格上有一个或多个城市小区。

输出

打印指示旅程的地图。如果有多张地图满足条件,则可以打印其中任何一张。


示例输入 1

11 7
.......
.......
*.....*
.......
..@....
.......
*......
.......
....*..
.......
.......

样本输入 1 的输出

.......
.......
*#####*
......#
..@...#
..#.###
*##.#..
#...#..
####*..
.......
.......

示例输入 2

7 11
........*..
...........
...........
...........
....*...*..
...........
..*.@...*..

样本输入 2 的输出

........*..
........#..
........#..
........#..
..##*##.*..
..#...#.#..
..*#@.##*..