UVa 10010

10010 - Where's Waldorf?

• http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=951

Summary

Given a m by n grid of letters, ( 1 <= m,n <= 50 ) and a list of words, find the location in the grid at which each of these words can be found.

Explanation

1. Add all the words in the word list to a Trie ( http://en.wikipedia.org/wiki/Trie ).

2. For all indices ( x, y ) in the character grid ( 0 <= x < m, 0 <= y < n ), start from the character at ( x, y ) and traverse through the grid in each of the 8 possible ways( Upwards, Downwards, Leftwards, Rightwards, and along the four diagonal directions ).

Simultaneously traverse through the Trie, one character at a time. Each time the end of a word in the Trie is reached, that means a word from the word list has been found. Update the value of ( x, y ) for this word, and continue.

In case, at any point in time, the path along the Trie and the current character in the grid do not match, break and start traversing in the next direction from ( x, y ), ( or move to the next grid position, if all 8 traversals for ( x, y ) have been completed ).

Gotchas

• Make sure that you do not stop a traversal as soon as a word has been found. Only do so if the grid boundaries are reached, or if there is a mismatch with the current character within the Trie. This is because the current word that has been found may be the prefix of an even longer string within the word list, which may also start at ( x, y ).

 For example, cat and catastrophe.

• Also make sure that you update the ( x, y ) co-ordinates of the words correctly, according to the specifications given in the problem statement. ( i.e, If a word occurs more than once in the grid, store the topmost occurence of the word; and if two occurences have the same x co-ordinate, store the leftmost such occurence. )

Implementations

An object-oriented language such as C++/JAVA is recommended, as this would make it easier to implement the Trie data structure.

Input

1

8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert

Output

2 5
2 3
1 2
7 8