Statistics

PROBLEM STATEMENT

You have been given a strange form of a word-search puzzle.  Not only can words
be formed up, down, left, right, and diagonally, but they can be formed in any
line, provided that the line passes exactly through the center of each letter
in the word, and ONLY through each letter in the word (or, more properly, the
center of the rectangular location in which each letter is displayed).

For example, if you wanted to find the word "BUM" in the following puzzle:
 0123456
0BEUHMGS
1UEUSNDF
2MWFDMSD

When referring to "rise" and "run", they are the number of rows down and
columns to the right, respectively. A row up would be considered a negative row
down, and a row left would be a negative row right. (See example 4 below)

You could find it in two locations, once in the top-left corner going down, and
once using a line with a rise of down 1 and run of right 2, thereby using the B
in the upper-left corner, the U in row 1 column 2, and the M in row 2 column 4.

In the above example, if the down one was to be returned, you would return
{0,0,1,0}, and if the second one was to be returned, you would return {0,0,1,2}.

Note: you could NOT use the split "B U M" across the top, as that line also
passes through the centers of the letters 'E' and 'H' and would form the word
"BEUHM".

If the word exists in more than one location, return the int[] {-1,-1,-1,-1},
as the word search must be messed up.  Therefore, in the above example, you
would actually return {-1,-1,-1,-1}.
If the word does NOT exist in the puzzle, return the int[] {-2,-2,-2,-2}.

Write a class WordSearch which contains the method indexOf.  This will take a
String[] representing the puzzle, and String representing the word to be found.
It will return an int[] of length 4 representing the location of the word.
The first two integers in this array will contain the row and column
coordinates of the first letter of the word.  The third integer will be the
rise of the slope of the line used, and the fourth, naturally, will be the run.

DEFINITION

Class: WordSearch
Method: indexOf
Parameters: String[], String
Return type: int[]
Method definition (be sure your method is public): int[] indexOf(String[]
puzzle, String word);

NOTES:
 
-If the word exists in more than one location, return the int[] {-1,-1,-1,-1},
as the word search must be messed up.  Therefore, in the above example, you
would actually return {-1,-1,-1,-1}.
-If the word does NOT exist in the puzzle, return the int[] {-2,-2,-2,-2}.
-All references to row numbers and column numbers are zero-based.

TopCoder will ensure the validity of the inputs.  Inputs are considered valid
if all of the following criteria are met:
-puzzle contains between 0 and 20 elements, inclusive.
-each element of puzzle contains between 1 and 20 characters, inclusive.
-each element of puzzle contains the same number of characters.
-puzzle consists of only the characters A-Z, inclusive.
-word is between 2 and 20 characters in length, inclusive.
-word consists of only the characters A-Z, inclusive.
-word is not a palindrome (think about it, and you'll understand why).

EXAMPLES:
1.
puzzle={"HDGERKDLSFE",
        "SDFOVKERJSK",
        "SFOEVNFJIWF",
        "WEBNREWBNER",
        "SDFOBIERNGD",
        "BOWERKBIERN",
        "SDFOENEDNCV",
        "GEREIEFKSEF",
        "FOWEIRNGNSI",
        "IOIRNBCIEOW",
        "OWOVCOITHNR",
        "OBKCNFJSGOE",
        "OPBODKFJIGN"}
word="GREEN"
returns {0,2,3,2}

If you start with the "G" in row 0, column 2, and go down 3 and over 2, you get
to "R".  Do it again, and you get to "E", then "E", then "N".  There is no
other location.

2.
puzzle={"HDGERKDLSFE",
        "SDFOVKERJSK",
        "SFOEVNFJIWF",
        "WEBNREWBNER",
        "SDFOBIERNGD",
        "BOWERKBIERN",
        "SDFNENEDNCV",
        "GEREIEFKSEF",
        "FOWEIRNGNSI",
        "IOIRNBCIEOW",
        "OWOGCOITHNR",
        "OBKCNFJSGOE",
        "OPBODKFJIGN"}
word="GREEN"
returns {-1,-1,-1,-1}
In addition to the other one, you can now find "GREEN" going up from row 10,
column 3.

3.
puzzle={"HDQERKDLSFE",
        "SDFOVKERJSK",
        "SFOEVNFJIWF",
        "WEBNREWBNER",
        "SDFOBIERNGD",
        "BOWERKBIERN",
        "SDFOENEDNCV",
        "GEREIEFKSEF",
        "FOWEIRNGNSI",
        "IOIRNBCIEOW",
        "OWOVCOITHNR",
        "OBKCNFJSGOE",
        "OPBODKFJIGN"}
word="GREEN"
returns {-2,-2,-2,-2}
We now have a puzzle devoid of the word "GREEN".

4. 
puzzle={"ABC",
        "DEF",
        "GHI"}
word="ID"
returns {2,2,-1,-2}

5.
puzzle={"FDHE",
        "BDEA",
        "QRLW",
        "SXLG",
        "QSOF"}
word="HELLO"
returns {0,2,1,0}

6.
puzzle={"GERJKSLH",
        "DQWOERKF",
        "BOITFKBI",
        "BOEDRIDQ",
        "OEIRDGRF",
        "SFESGOIE"}
word="FFE"
returns {4,7,-2,-3}

7.
puzzle={}
word="WHAT"
returns {-2,-2,-2,-2}