Boggle

Boggle is a board game played with letters and words. Sixteen letters are chosen at random and placed on a 44 game board; the players then form words by chaining up adjacent letters. ``Adjacent'' includes all eight directions of up, down, left, right, upper-left, upper-right, lower-left, and lower-right. The only restriction is that each position must not be used for more than once in the same word.

For example, consider the following board:

P R G N

G O E I

R S M Y

A M E D

Starting from the top-left corner, you can form ``programming''. But you cannot form ``programmer'', since the second ``r'' and the last ``r'' would conflict with each other at first row, second column. You can also start from other positions, e.g., you can form ``rose'' (several ways). But you cannot form ``rosemary'', since ``y'' is not adjacent to any ``r'' on the board.

You will take a word and a board, then determine if the word can be found on the board.

 
• Input
• Output
• Sample Input
• Sample Output