# C++ Program to check if word exists in Grid or not

Here we are going discuss about a 2D Grid or 2D array and check if a given word exists in Grid or not. Then we will write a C++ program to implement the same.

Given: A 2D Grid of character and a word to search for.

Problem: To check if the given word exists in the Grid or not.

Note: A word can be matched in 4 directions at any point, these directions are  Horizontally Left and Right, Vertically Up and Down.

Example:

```Word to search: cpp
Input: grid[][] = {"axmy",
"bcdf",
"xppt",
"raay"};
Output: Yes

a c m y
b g d f
x p e t
r a p s

Input: grid[][] = {"acmy",
"brdf",
"xeet",
"raps"};
Output : No```

Solution: Below are steps to find the solution:

• Check every cell, if the cell has first character, then recur one by one and try all 4 directions from that cell for a match.
• Mark the position in the grid as visited and recur in the 4 possible directions.
• After recurring, again mark the position as unvisited.
• Once all the letters in the word is matched, return true.

Now let’s implement the same steps in C++ programming language:

### C++ Program to check if word exists in Grid or not:

```#include <iostream>
using namespace std;
#define r 4
#define c 5

// Function to check if a word exists in a grid
// x, y: current position in 2D array
bool findmatch(char mat[r][c], string pat, int x, int y,
int nrow, int ncol, int level)
{
int l = pat.length();

// Pattern matched
if (level == l)
return true;

// Out of Boundary
if (x < 0 || y < 0 || x >= nrow || y >= ncol)
return false;

// If grid matches with a letter while recursion
if (mat[x][y] == pat[level]) {

// Marking this cell as visited
char temp = mat[x][y];
mat[x][y] = '#';

// finding subpattern in 4 directions
bool res = findmatch(mat, pat, x - 1, y, nrow, ncol, level + 1) |
findmatch(mat, pat, x + 1, y, nrow, ncol, level + 1) |
findmatch(mat, pat, x, y - 1, nrow, ncol, level + 1) |
findmatch(mat, pat, x, y + 1, nrow, ncol, level + 1);

// marking this cell as unvisited again
mat[x][y] = temp;
return res;
}
else // Not matching then false
return false;
}

// Function to check if the word exists in the grid or not
bool checkMatch(char mat[r][c], string pat, int nrow, int ncol)
{

int l = pat.length();

// if total characters in matrix is less then pattern length
if (l > nrow * ncol)
return false;

// Traverse in the grid
for (int i = 0; i < nrow; i++) {
for (int j = 0; j < ncol; j++) {

// If first letter matches, then recur and check
if (mat[i][j] == pat)
if (findmatch(mat, pat, i, j, nrow, ncol, 0))
return true;
}
}
return false;
}

int main()
{
char grid[r][c] = { "axmy",
"bcdf",
"xppt",
"raay" };

// Function to check if word exists or not
if (checkMatch(grid, "cpp", r, c))
cout << "Yes";
else
cout << "No";

return 0;

}
```

### OUTPUT:

`Yes`

Comment below in case if any issues or errors you are getting or to discuss more about the problem explained above.