Problem Statement

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).

Definition

Constraints

Examples