PROBLEM STATEMENT
You will be given the following information on a coordinate board:
*A laser location and firing direction
*A target location
*The location of walls that the laser cannot penetrate.
Calculate and return the minimum number of mirrors needed to make the laser hit
the target given that mirrors can only deflect the beam 90 degrees (so if the
beam is traveling right, a mirror can deflect it up or down). If the target is
unreachable by any mirror combination, return -1.
The board supplied will be a String[]. Each element will represent a row of
the board. The following characters may appear on the board:
. -- empty location
> -- laser firing right
^ -- laser firing up
< -- laser firing left
V -- laser firing down
X -- wall location
* -- target location
You may treat the coordinate of the laser as a wall, since no beam can
penetrate through the laser.
DEFINITION
Class name: Laser
Method name: minMirrors
Parameters: String[]
Returns: int
The method signature is:
int minMirrors(String[] board)
Be sure your method is public.
TopCoder will ensure the following:
*board contains between 5 and 20 elements, inclusive.
*each element of board will contain between 5 and 20 characters, inclusive, and
they will all contain the same number of characters.
*the board will be made up of the following characters only: ".X*^V<>" (quotes
added for clarity and will not appear on the board).
*there will be exactly one laser on the board
*there will be exactly one target on the board
EXAMPLES
(quotes added for clarity)
board=
{".......",
".......",
">....*.",
"...XXXX",
"......."}
The function returns 0, as there is a direct path to the target.
board=
{"...*.",
".....",
"..X.X",
"..X.X",
"..X.X",
"..X.X",
"..X.X",
"..X.X",
">...X",
"XXX.."}
The function returns 1.
board=
{"...............",
"...............",
"...............",
"...............",
".>.............",
"...XXXXXXX.....",
"....X*..X......",
"....XXX........",
"...............",
"..............."}
If / and \ signify mirrors, - and | signify laser path, one of the shortest
path options is as follows (it is not a unique shortest path):
...............
...............
...............
...............
.>--------\....
...XXXXXXX|....
....X*-\X.|....
....XXX\--/....
...............
...............
The method returns 4.
board=
{"...............",
"...............",
"...............",
"...............",
".>.............",
"...XXXXXXX.....",
"....X*.XX......",
"....XXX........",
"...............",
"..............."}
There is no path to the target, and the function returns -1.