407160: GYM102697 131 The Mirrors Strike Back

If you competed in the CodeRams Contest #8, you might remember a problem involving mirrors and light. This is a more difficult and updated version of that problem.

You are in a hall of mirrors, and you shine a laser beam in a certain direction. Given the position of several diagonal mirrors, figure out the path of the laser beam.

You shine your laser beam from the back of the hall of mirrors (on a computer screen, this will look like the "bottom" of the image).

This problem also adds "star blocks", which shine light in all directions when light passes through them.

The first line of input contains two space-separated integers $$$n$$$, $$$m$$$, and $$$x$$$. $$$n$$$ and $$$m$$$ represent the number of rows and columns, respectively, and the number $$$x$$$ represents the index on the bottom row that you start shining the laser pointer at (with 0-based indices). The next $$$n$$$ lines contain $$$m$$$ characters representing the hall of mirrors. If a position does not contain a mirror, it will be pictured as a single dot. If it does have a mirror, it will be represented with either a forward slash ("/") or a backslash, which represents the direction that it reflects light in. See the example cases if you are confused on this. Additionally, if the position contains a star block, it will be pictured as an asterisk ("*"). Star blocks redirect light in all four immediate directions (up, down, left, and right).

Output the given input matrix, however, replace any positions without a mirror or star block that the laser pointer shines through horizontally with a hyphen, and replace any positions without a mirror or star block that the laser pointer shines through vertically with a pipe ("|"), above the ENTER key on a keyboard. If the laser pointer travels through a space in both directions, replace the dot in that position with a plus symbol ("+").

10 10 5
......./..
..........
/....\....
..........
..........
..........
..........
\......*..
..........
..........

......./--
.......|..
/----\.|..
|....|.|..
|....|.|..
|....|.|..
|....|.|..
\----+-*--
.....|.|..
.....|.|..

10 10 2
../....\..
..........
/.*..\....
..........
..........
..........
..........
\......*..
..........
..........

../----\..
..|....|..
/-*--\.|..
|.|..|.|..
|.|..|.|..
|.|..|.|..
|.|..|.|..
\-+--+-*--
..|..|.|..
..|..|.|..