LAS - Laser

Original problem statement (in Polish) can be found here. (It contains some more story that was removed from this version, because certain pun does not make any sense in English).

There is a grid with n rows and m columns, consisting of 1x1 squares. There is exactly one square with a laser and one (different) square with a sensor. The laser emits a beam of concentrated light from the middle of its square, in one of the four directions (north, south, east or west). Some squares are blocked, so they don't let the light through. (In that sense, square with a laser is also considered blocked).

We have a number of two-sided mirrors. We can place them on the middle of a square, in one of the two configurations (45 degrees). Mirrors placed in such a way reflect the light, making a right angle (90 degrees).

Your task is to guide the light to the sensor, using the minimum number of mirrors.

Input

The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.

The description of a single testcase begins with two integers n, m (1 <= n, m <= 200) - number of rows and columns, respectively. Then, n lines follow, each containing m characters. j-th character in i-th line denotes a square in i-th row nad j-th column. "." (a dot) denotes free square, "#" denotes blocked square. There is exactly one laser on the grid, represented by one of these four characters: "<", ">", "v" or "^" (it depends on the direction of the laser). There is also exactly one sensor, represented by "C". No other characters can appear in a line.

Output

For every testcase you should print n lines with m characters, denoting the grid from the input, but with mirrors placed on some of the fields. Mirrors are represented by "\" and "/" characters. Arrangement of mirrors should make the light reach the sensor, while using minimum possible number of mirrors. You can't place mirrors on blocked fields, as well as on field with the laser and on field with the sensor. There is always a way for the light to reach the sensor.

Example

Input:

2
3 4
>...
###.
C...
5 5
v#...
.#.#.
.#.#.
.#.#.
...#C

Output:

>..\
###.
C../

v#/.\
.#.#.
.#.#.
.#.#.
\./#C

Added by:Piotr Jagiełło
Date:2016-07-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:PIZZA 2016 qualifying round

hide comments
2021-12-10 23:58:06 Piotr Jagie³³o
Lowercase "v" is normal, it's even in the sample input (there is no uppercase V).
But there's no lowercase "c" in the input data for sure.
2021-10-14 03:13:24
Good bfs problem.

It takes me many days to debug.

There may be lowercase 'v' or 'c' in input data.
2021-09-23 10:04:44
Really a troubling problem....Take a long time to debug but still get WA.....
2017-04-22 22:45:45
Nice one
2016-08-14 01:13:56 Archit Jain
awesome
2016-07-27 12:20:44 Piotr Jagie³³o
Any correct output will be accepted.
2016-07-26 19:26:17 Sushovan Sen
What is expected output if multiple such solutions exist?
Test case :
1
5 5
. . . . .
. . C . .
. . # . .
. . V . .
. . . . .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.