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[0]) 
                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.