Answer to Question #93901 in Algorithms for rosy

Question

Amanada, a school kid, is learning English alphabets. Her teacher devised a small game to make the task fun. A grid of ‘m’ rows and ‘n’ columns is filled with English alphabets.She needs to search English words in this grid by moving one step at a time in any of the adjacent grid cells.A grid of alphabets and a set of English words are given. Amanda can start from anywhere in the grid and can move in any of the 8 adjacent grid cells, one step at a time. Each grid cell can only be used once.

Answer 1

@@ Assume that the grid and the dictionary are global variables @@

 

rsearch(cell, subword):

   Return if the current cell has been visited

   Mark the current cell as visited

   Append the current character to the subword

   Output the subword if it is in the dictionary

   Recursively call rsearch(...) for each of 8 adjacent cells

   Remove the last character from the subword

 

search(start):

   Call rsearch(...) for the starting cell