In the word game Boggle, a player is presented with a 4x4 grid of letters and has the task of finding words hidden among the letters. A word may start at any location, and each succeeding letter of the word must be adjacent to the preceding letter horizontally, vertically, or diagonally.
In our version of the game, a player is restricted to finding words from a given list of acceptable words. The same letter may be used multiple times in the spelling of a word, and it is permitted to spell words that are part of longer words. For instance, in the following example, one could form the word SANDS, even though there is only a single S:
XXXX XSAX XDNX XXXX
Notice that the above configuration would also yield other words, like SAND, AND, and SAD.
If a word can be formed in more than one way, it may be counted more than once; for instance, the word EYE may be counted multiple times here since it can be found in different directions (see examples):
XEYE XXXX XXXX XXXX
Here, the word EYE could still be formed, but only once, since we are allowed to reuse letters:
XXEY XXXX XXXX XXXX
Here, the word TREE may be formed two different ways (down-right-up or down-diagonal-down):
TEXX REXX XXXX XXXX
The score for each word is the square of its length. Thus, three letter words are worth 9 points, four letter words are 16 points, etc.
You are given a String grid with exactly four elements, with each element containing 4 letters, describing the grid of letters you are to search. You are also given a String words, each element of which represents an acceptable word.
You are to return a long indicating the maximum score you can achieve after finding all possible paths to spell out acceptable words, summing together the scores from each individual word. Since the maximum score could potentially be quite large, return the result MOD 1E13 (10000000000000).
|-||grid will contain exactly four elements.|
|-||Each element of grid will contain exactly four characters.|
|-||Each character of each element of grid will be an uppercase ('A'-'Z') letter.|
|-||words will contain between 1 and 50 elements, inclusive.|
|-||Each element of words will contain between 1 and 50 characters, inclusive.|
|-||Each character of each element of words will be an uppercase ('A'-'Z') letter.|
|-||No two elements of words will be the same.|