Statistics

PROBLEM STATEMENT
You are going to write a program that analyzes mazes.  The mazes are composed
of free squares, obstacles squares, locked squares, a starting location, and a
destination.  You begin on the starting location.  It is legal to move left,
right, up or down one square at a time.  It is illegal to move onto an obstacle
square or leave the confines of the maze.  Moving onto a locked square is
legal, but it will use one key.  

A SOLUTION to a given maze is a path from the starting location to the
destination consisting of only legal moves and never moves onto the same square
more than once.  
A MINIMAL SOLUTION is a SOLUTION such that no other SOLUTION to the maze uses
FEWER keys.
A LEFT MINIMAL SOLUTION is a MINIMAL SOLUTION such that no other MINIMAL
SOLUTION to the maze moves left FEWER times.  The number of left moves is how
many times you move left in your path from the starting position to the
destination.

Your method will return the number of left moves in the LEFT MINIMAL
SOLUTION(s) to the given maze.  If no SOLUTION exists it will return -1.

Lets say you had a maze like the one pictured below on the left:
'X' is an obstacle square, '.' is a free square,
'$' is a locked square, 'Y' is the starting position, and 'W' is the destination

W$..$     .....
$$...     U....  'U','L', and 'R' correspond up, left, and right respectively
.....     ULLL.
$.XY.     ...U.  

All of the SOLUTIONs to this maze begin by moving up or right, since moving
down leaves the maze, and there is an obstacle to the left.  The MINIMAL
SOLUTIONs use 1 key whereas the non MINIMAL SOLUTIONs use anywhere from 2 to 5
keys.  The LEFT MINIMAL SOLUTIONs make 3 left moves so your method would return
3.  The picture above on the right shows the path taken by one particular LEFT
MINIMAL SOLUTION.

Create a class LeftMoves that contains the method howMany, which takes an
String[] maze, and returns a int representing the number of left moves in a
LEFT MINIMAL SOLUTION to the given maze.  If no SOLUTION exists your method
returns -1.

DEFINITION
Class: LeftMoves
Method: howMany
Parameters: String[]
Returns: int
Method signature (be sure your method is public):  int howMany(String[] maze);

NOTES
- A given maze can have many SOLUTIONs, MINIMAL SOLUTIONs, and LEFT MINIMAL
SOLUTIONs

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- maze will contain between 1 and 50 elements inclusive
- Each element of maze will have length between 1 and 50 inclusive
- Each element of maze will have the same length
- Each element of maze will only contain characters from the following string:
"W$.XY" (quotes for clarity)
- The character 'Y' will occur exactly once in maze (quotes for clarity)
- The character 'W' will occur exactly once in maze (quotes for clarity)

EXAMPLES
1) maze = {"W$..$",
           "$$...",
           "....."
           "$.XY."}

This is the example given above.  Method returns 3.

2) maze = {"$$$W...",
           "$XXXXX.",
           "$XXXXX.",
           "$XXXXX.",
           "Y......"}

There are 2 SOLUTIONs to this maze.  The only MINIMAL SOLUTION moves
counter-clockwise around the central obstacle on its way to the destination.
This path makes 3 left moves thus the method returns 3.

3) maze = {"WX...",
           "X....",
           "....Y"}
           
The two obstacles block all paths to the destination.  Method returns -1.

4) maze = {"$$$$$$$W$$$$$$$",
           "$$$$$$$$$$$$$$$",
           "$$$$$$$$$$$$$$$",
           "$$$$$$$$$$$$$$$",
           "$$$$$$$$$$$$$$$",
           "$$$$$$XXXXXX$$$",
           "$$$$$$$$$$$$$$$",
           "$$$$$$$$$Y$$$$$"}

Method returns 4.

5) maze = {"XYWX"}

Method returns 0.

6) maze = {"..Y$W...",
           ".XXXXXX.",
           "........"}

Method returns 5.