Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Backtracking — Search a Word In a Matrix

Objec­tive : Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and diagonally).

Exam­ple:

Search a Word In a Matrix

Search a Word In a Matrix

Approach:

We will show the path as incre­ment counter

Search a Word In a Matrix - Solution

Search a Word In a Matrix — Solution

 

  • Cre­ate a solu­tion matrix of the same struc­ture as Matrix.
  • Try each cell a start­ing point.
  • Check cur­rent cell is not already used and char­ac­ter in it matches with the char­ac­ter in the word at index (starts will 0).
  • Check if index = length of the word, means we have found the word. return true and print the solu­tion matrix.
  • If above cri­te­ria matches, mark that cell with a num­ber When­ever any cell matches with the cri­te­ria, put a num­ber cor­re­spond­ing to it in solu­tion matrix. (start with 0 and keep incre­ment­ing it, it will show us the path for the word).
    • Now try to solve rest of the prob­lem recur­sively by mak­ing index +1. Check all 8 direc­tions ( up, down, left right, diag­o­nally up-left, diag­o­nally up-right, diag­o­nally down-left, diag­o­nally down-right). Check the bound­ary con­di­tions as well
    • If none of the 8 recur­sive calls return true, BACKTRACK and undo the changes ( put 0 to cor­re­spond­ing cell in solu­tion matrix) and return false.
  • Choose dif­fer­ent start­ing point.
  • If all the start­ing points tried and solu­tion not found, return false
  • See the code for bet­ter understanding.

Code:

Output:

 0 0 0 0 0
 0 1 0 5 0
 0 0 2 4 6
 0 0 0 3 7
 0 0 0 0 0

You may also like...