Super Boggle

Boggle is your favorite childhood pastime! In Boggle, up to four players attempt to find words in sequences of adjacent letters in a scrambled 4×4 grid of lettered dice. The game was fun when you were six years old, but due to your amazing algorithmically gifted brain, you realize one day that nobody was able to beat you in this game. Boggle was just no fun anymore, so you decided to invent your own version - Super Boggle!

In Super Boggle, players are given an arbitrarily sized grid of random letters. Then, he or she is required to follow the normal rules of Boggle to find words within the grid. However, in your version of the game, letters do not have to be adjacent to be part of the same word! As a result of this modification, players are not only scored by the length of the word they make, but also by how little the distances are between all of their letters on the grid. The specific scoring rules do not matter for now, but the word formation rules do.

To create a word, a player must start at a letter, jump across the board to another letter, add it to the end of the first letter and record the distance of the jump. They must repeatedly jump across the board, adding the distances together and appending those letters to the end of their word so far until they form the word they desire. The distance from any letter to an adjacent letter (horizontally, vertically or diagonally) is 1. They may jump over letter(s) they've already jumped over, but they may not reuse a letter found at the same position on the grid for their word. The goal is to create the word with the minimal total distance between all its letters.

You've played a few rounds, and think that you're already pretty good at your game, but out of curiousity, you want to build a program that will tell you the actual shortest distances to form specific words.

Input Format

The first line of the input will contain the integer N (1 ≤ N ≤ 10).
The next N lines with contain N uppercase characters from A-Z, denoting the Super Boggle grid.
The next line will contain the integer T (1 ≤ T ≤ 100).
The next T lines will each contain a string of no more than 20 uppercase letters from A to Z.
Bonus: one case will have N ≤ 100 and T ≤ 10.

Output Format

For every word in the input after T, print on a new line the shortest distance required to form that word, or "IMPOSSIBLE" otherwise.

Sample Input

4
AEDF
DGAY
AEED
RFND
5
HELLO
FADED
GRADED
DEGRADED
GRANDDADDY

Sample Output

IMPOSSIBLE
4
6
8
13

Explanation

In the last test case to form GRANDDADDY, we take the path [2,2] → [4,1] → [3,1] → [4,3] → [4,4] → [3,4] → [2,3] → [2,1] → [1,3] → [2,4] for a distance of 2+1+2+1+1+1+2+2+1 = 13. (Fig. 1)

The path [2,2] → [4,1] → [3,1] → [4,3] → [2,1] → [3,1] → [2,3] → [4,4] → [3,4] → [2,4] also forms the word legally, but has a longer distance of 2+1+2+2+2+1+2+1+1 = 14. (Fig. 2)

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 15, 2012
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)