Search Word In Matrix problem states that “Given a 2D matrix filled with some characters. Check whether the word exist in the matrix or not”. All movements right, left, up, down and diagonally are possible. For example The below given matrix filled with some characters find how many times “home” occurs. The word “home” in given matrix occurs two times. Print 0 if matrix does not contain pattern (word).

Search Word In Matrix

How to Search Word In Matrix

  • If any index (i,j) of given matrix is equal to the first letter of string to be searched.
  • Search for next match.
  • Else Backtrack.

Test Case:

3
6 8
home
h w w q p w w w
w o w w d c w w
p w m e o m b a
g w e f w w h w
w g w w c w h c
w w f w g w w w
4 4
dod
a s d r
a d o g
a s g r
e r t t
4 4
dog
a s d r
a d o g
a s g r
e r t t

Output:

2
2
4
#include<iostream>
#include<cstdio>
using namespace std;

#define row 20
#define col 20

char mat[row][col];
char str[50];
bool v[row][col];
int r = 0;
int c = 0;
int cnt = 0;

bool isSafe (int i, int j, int r, int c)
{
  if (i < 0)
    return false;
  if (j < 0)
    return false;
  if (i > r || j > c)
    return false;

  return true;
}

void searchWord (int i, int j, char *str, int strsize, int k)
{
  // helper array for (i,j) in 8 direction
  int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// if the size of str is eqaul to k , increment counter cnt
  if (k == strsize)
    {
      cnt++;
      return;
    }

// search around i,j in 8 direction
  for (int p = 0; p < 8; p++)
    {
      int x = dx[p] + i;
      int y = dy[p] + j;
      if (isSafe (x, y, r, c))
	{
	  if (mat[x][y] == str[k + 1] && !v[x][y])
	    {
	      v[x][y] = 1;
	      searchWord (x, y, str, strsize, k + 1);
	      v[x][y] = 0;
	    }
	}
    }
  return;
}

int main ()
{
  freopen ("input.txt", "r", stdin);
  int testcase = 0;
  cin >> testcase;
  for (int t = 0; t < testcase; t++)
    {
      int ans = 0;
/********************read test case ************/
      // read grid size
      cin >> r >> c;
      // read pattern to search
      cin >> str;
      // read grid input
      for (int i = 0; i < r; i++)
	{
	  for (int j = 0; j < c; j++)
	    {
	      cin >> mat[i][j];
              // make visited false
	      v[i][j] = 0;
	    }
	}
      // calculate size of str exclusing newline ('\0')
      int strlen = 0;
      while (str[strlen] != '\0')
	{
	  strlen++;
	}
      for (int i = 0; i < r; i++)
	{
	  for (int j = 0; j < c; j++)
	    {
              // if start index is equal to 
              //the first letter of str
	      if (mat[i][j] == str[0] && !v[i][j])
		{
		  v[i][j] = 1;
                  // then search for next match
		  searchWord (i, j, str, (strlen - 1), 0);
		  v[i][j] = 0; // backtrack
		}
	    }
	}
      ans = cnt;
      cout << ans << endl;
      cnt = 0;

    }	// test t end

  return 0;
}

Note: Submit your article at myconcept@wikistack.com



Related Contents to follow