Check if a word exists in a grid or not | C ++ program to check if the word exists in the grid or not ; Function to check if a word exists in a grid starting from the first match in the grid level : index till which pattern is matched x , y : current position in 2D array ; Pattern matched ; Out of Boundary ; If grid matches with a letter while recursion ; Marking this cell as visited ; finding subpattern in 4 directions ; marking this cell as unvisited again ; else Not matching then false ; Function to check if the word exists in the grid or not ; if total characters in matrix is less then pattern lenghth ; Traverse in the grid ; If first letter matches , then recur and check ; Driver Code ; Function to check if word exists or not
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define r  4 NEW_LINE #define c  5 NEW_LINE bool findmatch ( char mat [ r ] , string pat , int x , int y , int nrow , int ncol , int level ) { int l = pat . length ( ) ; if ( level == l ) return true ; if ( x < 0 y < 0 x > = nrow y > = ncol ) return false ; if ( mat [ x ] [ y ] == pat [ level ] ) { char temp = mat [ x ] [ y ] ; mat [ x ] [ y ] = ' # ' ; 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 ) ; mat [ x ] [ y ] = temp ; return res ; } return false ; } bool checkMatch ( char mat [ r ] , string pat , int nrow , int ncol ) { int l = pat . length ( ) ; if ( l > nrow * ncol ) return false ; for ( int i = 0 ; i < nrow ; i ++ ) { for ( int j = 0 ; j < ncol ; j ++ ) { if ( mat [ i ] [ j ] == pat [ 0 ] ) if ( findmatch ( mat , pat , i , j , nrow , ncol , 0 ) ) return true ; } } return false ; } int main ( ) { char grid [ r ] = { " axmy " , " bgdf " , " xeet " , " raks " } ; if ( checkMatch ( grid , " geeks " , r , c ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }