UVa 10010

From Algorithmist
Jump to navigation Jump to search

10010 - Where's Waldorf?[edit]

Summary[edit]

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[edit]

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[edit]

  • 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[edit]

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

Brute force note[edit]

A less elegant (O( |words-to-look-for| ) times slower, but slightly more memory-efficient) solution that still works is a brute-force C++ array implementation. Read the grid into a character array (converting to lowercase along the way). When looking for a word, start traversal at (i, j) where i=0..m-1, j=0..n-1 with dRow=-1,0,1, dCol=-1,0,1 (not both 0). Print if found. Order of starting points (i, j) for the traversal guarantees that one can print results immediately (rather than keep coordinates and sort them).


Input[edit]

1

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

Output[edit]

2 5
2 3
1 2
7 8

Solutions[edit]