Problem AO
Board Covering
Given a board with $M$ rows and $N$ columns. A cell at the $i^{th}$ row from the top and the $j^{th}$ column from the left is denoted by $(i, j)$. Each cell of the board is one of $3$ types:
-
A blocked cell.
-
An empty cell.
-
A number in range $[1, 9]$.
For example:
![\includegraphics[width=0.6\textwidth ]{1_anotated.png}](/problems/boardcovering/file/statement/en/img-0001.png)
Your task is to fill all empty cells on the board. For each cell $(i, j)$ containing a number, you need to:
-
Draw $1$ to $4$ lines starting from cell $(i, j)$. These lines must be parallel to side of boards and go to adjacent cells.
-
The lines can only go through empty cells.
-
The sum of length of these lines must be exactly equal to the number written on cell $(i, j)$.
-
No two lines can intersect (i.e., no two lines can have a common cell).
For example, starting from cell $(1, 1)$, you can draw 1 line like following image. The number in cell $(1, 1)$ became $0$, this indicates that the requirement for this cell is satisfied.
![\includegraphics[width=0.3\textwidth ]{2.png}](/problems/boardcovering/file/statement/en/img-0002.png)
The next figure shows the lines from cell $(4, 1)$ and cell $(5, 2)$:
![\includegraphics[width=0.3\textwidth ]{3.png}](/problems/boardcovering/file/statement/en/img-0003.png)
The next figure shows the lines from cell $(3, 2)$. Note that $2$ lines are drawn, whose sum is exactly $2$.
![\includegraphics[width=0.3\textwidth ]{4.png}](/problems/boardcovering/file/statement/en/img-0004.png)
The final figure shows the completely filled board:
![\includegraphics[width=0.3\textwidth ]{5.png}](/problems/boardcovering/file/statement/en/img-0005.png)
Input
The first line of input contains $2$ integers $M$ and $N$ - the number of rows and columns of the board $(1 \le M, N \le 12)$. The next $M$ lines, each contains $N$ characters representing the board. Each character can be one of the following:
-
‘#’ denoting a blocked cell.
-
‘.’ denoting an empty cell.
-
A digit from $1$ to $9$, the number written on this cell.
Output
Output exactly $M$ lines, each line contains exactly $N$ character.
-
Output ‘#’ for a blocked cell.
-
Output a digit for the number written on the cell.
-
For the empty cells, output one of $4$ characters ‘<’, ‘>’, ‘^’, ‘v’, the direction of the line from the number to this cell. See sample output for more clarity.
It is guaranteed that at least one solution exists. In case of multiple solutions, you can output any of them.
Sample Clarification
The sample dataset corresponds to the figures in the problem statement.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 1.##. .##.3 .2... 2..3. .1#.1 |
1>##^ ^##^3 ^2>^v 2v<3v <1#<1 |