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 twosided 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. jth character in ith line denotes a square in ith row nad jth 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
hide comments
cjn2007:
20211014 03:13:24
Good bfs problem.


psz2007:
20210923 10:04:44
Really a troubling problem....Take a long time to debug but still get WA..... 

hodobox:
20170422 22:45:45
Nice one 

Archit Jain:
20160814 01:13:56
awesome 

Piotr Jagie³³o:
20160727 12:20:44
Any correct output will be accepted. 

Sushovan Sen:
20160726 19:26:17
What is expected output if multiple such solutions exist?

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