Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid.
The word can be formed in any of the 8 possible directions as shown below.
Here is how I solved this problem.
Write a function which takes the string to be searched, the starting coordinates, and the direction number (as shown above) as parameters.
bool search_grid(const char *word, int x, int y, int direction)
If the current letter matches, depends on the direction, we recursively invoke the same method for the next character in the string with modified coordinates.
If the current letter does not match, the word cannot be found in the given direction starting from the initial coordinates.
Here is the C++ program which implements the basic algorithm for the word match. This is not a complete program. You may try writing a wrapper which finds the initial coordinates to start the word search (Find the the coordinates where the first letter of the word appears) and do some checks for base cases like empty string etc.