Question: There is a 2D grid of characters. You need to find if a given word can be matched in any direction in the grid. The direction can be up-down, down-up, left-right, right-left, both diagonals up and down. This problem is also famous with the name 'Where's Waldorf?'.

Example: You are given a character grid like below. You need to find patterns 'Akash and 'coDe' in this grid. They can appear in any direction. Also the search should be case insensitive.


Below are the result of finding 'Akash and 'coDe'.

 
 


Input: The input begins with a pair of integers, m followed by n, 1 < m,n < 50 in decimal notation on a single line. The next m lines contain n letters each; this is the grid of letters in which the words of the list must be found. After that another integer k appears on a line by itself (1 < k < 20). The next k lines of input contain the list of words to search for, one word per line to be found in the grid in case insensitive manner.

For our example, sample input will be:
5 5
HQWCS
ESPKD
DXAFL
OCHKH
CTYCA
2
Akash
coDe

Output:
For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output.

For our example, sample output will be:
5 5
5 1

Algorithm:
This is a very straight forward problem. We first need to find the first character match of word (to be found) in the grid. One we find the start point, we need to go in all 8 directions till the end of word (or the grid). If we reach end of the word, print the starting coordinates and move on to next word.

Code (C++):

#include <iostream>

using namespace std;
#define N 50

// We can search is all 8 directions
char DIR[8][2] = {
  {1,0}, {1,-1}, {1,1}, {0,-1}, {0,1}, {-1,0}, {-1,-1}, {-1,1}
};
// for toal array size
int m, n;

// method for finding word presence in the array in a specific direction
bool match(char CharMat[50][50], char word[], int i, int j, int dir_index)
{
  int k=0;
  for( ; i<m  && j<n  && i>=0  && j >=0  && word[k] != '\0'; i = i+DIR[dir_index][0],  j = j+DIR[dir_index][1], k++)
    if(toupper(word[k]) != toupper(CharMat[i][j]))
      return false;

  if (word[k] == '\0')
    return true;

  return false;  
}

void find_presence(char CharMat[50][50], char word[])
{
  for(int i=0; i<m; i++)
    for(int j=0; j<n; j++)
      if (toupper(CharMat[i][j]) == toupper(word[0]))
        for (int k=0; k<8; k++)
          if (match(CharMat, word, i, j, k))
          {
            cout << i+1 << " " << j+1 << endl;
            return;
          }
  cout << "'" << word << "' was not found in the grid" << endl;
}

int main()
{
  char CharMat[N][N];
  cin >> m;
  cin >> n;
  for (int i=0; i<m; i++)
    cin >> CharMat[i];
  
  int num_words;
  char word[N];
  cin >> num_words;
  for (int j=0; j<num_words; j++)
  {
    cin >> word;
    find_presence(CharMat, word);
  }
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.