Find all occurrences of a given word in a matrix | Python3 Program to find all occurrences of the word in a matrix ; check whether given cell ( row , col ) is a valid cell or not . ; return true if row number and column number is in range ; These arrays are used to get row and column numbers of 8 neighboursof a given cell ; A utility function to do DFS for a 2D boolean matrix . It only considers the 8 neighbours as adjacent vertices ; return if current character doesn 't match with  the next character in the word ; append current character position to path ; current character matches with the last character \ in the word ; Recur for all connected neighbours ; The main function to find all occurrences of the word in a matrix ; traverse through the all cells of given matrix ; occurrence of first character in matrix ; check and prif path exists ; Driver code
ROW = 3 NEW_LINE COL = 5 NEW_LINE def isvalid ( row , col , prevRow , prevCol ) : NEW_LINE INDENT return ( row >= 0 ) and ( row < ROW ) and ( col >= 0 ) and ( col < COL ) and not ( row == prevRow and col == prevCol ) NEW_LINE DEDENT rowNum = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ] NEW_LINE colNum = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ] NEW_LINE def DFS ( mat , row , col , prevRow , prevCol , word , path , index , n ) : NEW_LINE INDENT if ( index > n or mat [ row ] [ col ] != word [ index ] ) : NEW_LINE INDENT return NEW_LINE DEDENT path += word [ index ] + " ( " + str ( row ) + " , ▁ " + str ( col ) + " ) ▁ " NEW_LINE if ( index == n ) : NEW_LINE INDENT print ( path ) NEW_LINE return NEW_LINE DEDENT for k in range ( 8 ) : NEW_LINE INDENT if ( isvalid ( row + rowNum [ k ] , col + colNum [ k ] , prevRow , prevCol ) ) : NEW_LINE INDENT DFS ( mat , row + rowNum [ k ] , col + colNum [ k ] , row , col , word , path , index + 1 , n ) NEW_LINE DEDENT DEDENT DEDENT def findWords ( mat , word , n ) : NEW_LINE INDENT for i in range ( ROW ) : NEW_LINE INDENT for j in range ( COL ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == word [ 0 ] ) : NEW_LINE INDENT DFS ( mat , i , j , - 1 , - 1 , word , " " , 0 , n ) NEW_LINE DEDENT DEDENT DEDENT DEDENT mat = [ [ ' B ' , ' N ' , ' E ' , ' Y ' , ' S ' ] , [ ' H ' , ' E ' , ' D ' , ' E ' , ' S ' ] , [ ' S ' , ' G ' , ' N ' , ' D ' , ' E ' ] ] NEW_LINE word = list ( " DES " ) NEW_LINE findWords ( mat , word , len ( word ) - 1 ) NEW_LINE