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).

## 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.

```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;
cin >> r >> c;
cin >> str;
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