Problem Description

Circuit Layout and Routing is a crucial concept in the field of Electronic Design Automation (EDA), involving the process of arranging and connecting electronic components on a circuit board or integrated circuit. The goal of this process is to optimize space, cost, and manufacturing processes while meeting requirements such as electrical performance, signal integrity, and electromagnetic compatibility.

Xiao Xiao now needs to solve a simplified circuit wiring problem on an $n × m$ grid. The grid consists of:
- Hash # marked cells that are already occupied and cannot be wired.
- Plus + marked cells that are connected to other parts of the circuit and must be wired. There is at least one cell that must be wired in the given problem.
- Dot . marked cells that Xiao Xiao can choose whether to wire: wiring means marking the cell as a plus, not wiring means keeping it as a dot.

Xiao Xiao's task is to choose as many cells as possible for wiring (marking . cells as +), satisfying:
1. The wired circuit is connected. That is, from any wired cell, it is possible to reach any other wired cell by moving up, down, left, or right to adjacent wired cells.
2. The wiring does not have short circuits (loops), i.e., there is no wired cell that can return to itself by moving more than 2 steps up, down, left, or right to adjacent wired cells, with all cells visited being distinct.

For example, the following is a circuit wiring problem with three cells already marked as must-wire (plus):

#....#
....+#
.+####
.+...#

The following shows a valid and two invalid wiring schemes:

#+.+.# #.+..# #++..#
+++++# ..+++# .++++#
.+#### .+#### .+####
.++++# .+...# .+...#
Valid Not connected Has loop

Input Format

The first line of input contains two space-separated integers $n$ and $m$, representing the number of rows and columns of the grid, respectively.

The next $n$ lines, each containing $m$ characters (#, +, or .), describe the specific wiring problem.

The input data guarantees that there is at least one valid wiring scheme. There is at least one + in the input.

Output Format

Output $n$ lines, each containing $m$ characters, representing the optimal wiring scheme with as many wired cells as possible. If there are multiple possible solutions, output any one of them.

Sample Input and Output

Sample Input #1

2 2
+.
..

Sample Output #1

+.
++

Sample Input #2

3 5
...+#
..###
....+

Sample Output #2

++++#
.+###
+++++

Sample Input #3

5 6
..++..
.#..#.
.#..#.
.#..#.
......

Sample Output #3

++++++
+#.+#+
+#+.#+
+#++#+
++.+++

Notes

Data Size

For $40\%$ of the data, $n × m \le 16$.

For $100\%$ of the data, $1 \le n, m \le 6$.

Scoring Criteria

On the premise that your wiring scheme is valid (connected and without loops):

• If your scheme is the optimal wiring scheme, i.e., with the most wired cells, you get full marks for that test case.
• Otherwise, you get half the marks for that test case.

The original full score for this problem is $20\text{pts}$.

SPJ Provider: @scp020

见题面 Input 部分

见题面 Output 部分