TrieBacktrackingMatrix
Given a grid of letters and a list of words, find every word from the list that can be traced in the grid by moving between horizontally or vertically adjacent cells, using each cell at most once per word. Print the words you found in alphabetical order.
Input
Line 1: r and c. Next r lines: each a row of c lowercase letters (no spaces). Then a line with m, the number of words, and a line with the m words.
Output
Print each found word on its own line in alphabetical order, or None if no word can be found.
Constraints
1 <= r, c <= 6 1 <= m <= 40 1 <= length of each word <= 8
Example 1
Input
4 4 oaan etae ihkr iflv 4 oath pea eat rain
Output
eat oath
oath and eat can be traced; pea and rain cannot.