Find all occurrences of given string in a character matrix

Given a M x N matrix of characters, find all occurrences of a given string in the matrix. We are allowed to search the string in all eight possible directions i.e. North, West, South, East, North-East, North-West, South-East, South-West. Note that there should not be any cycles in the output path.


For example, consider below matrix of characters,

[ ‘D’, ‘E’, ‘M’, ‘X’, ‘B’ ]
[ ‘A’, ‘O’, ‘E’, ‘P’, ‘E’ ]
[ ‘D’, ‘D’, ‘C’, ‘O’, ‘D’ ]
[ ‘E’, ‘B’, ‘E’, ‘D’, ‘S’ ]
[ ‘C’, ‘P’, ‘Y’, ‘E’, ‘N’ ]

If given string is “CODE”, below are all its occurrences in the matrix –


‘C'(2, 2) ‘O'(1, 1) ‘D'(0, 0) ‘E'(0, 1)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 0) ‘E'(3, 0)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(1, 2)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(3, 0)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(3, 2)
‘C'(2, 2) ‘O'(2, 3) ‘D'(2, 4) ‘E'(1, 4)
‘C'(2, 2) ‘O'(2, 3) ‘D'(3, 3) ‘E'(3, 2)
‘C'(2, 2) ‘O'(2, 3) ‘D'(3, 3) ‘E'(4, 3)

 


 
We can use DFS to solve this problem. The idea is to start from each cell in the matrix and explore all eight paths possible and recursively check if they will leads to the solution or not. To make sure that the path is simple and doesn’t contain any cycles, we keep track of cells involved in current path in an matrix and before exploring any cell, we ignore the cell if it is already covered in current path.

We can find all the possible locations we can move to from the given location by using the array that stores the relative position of movement from any location. For example, if the current location is
(x, y), we can move to (x + row[k], y + col[k]) for 0 <= k <=7 using below array.

int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

So, from position (x, y), we can move to:

(x – 1, y – 1)
(x – 1, y)
(x – 1, y + 1)
(x, y – 1)
(x, y + 1)
(x + 1, y – 1)
(x + 1, y)
(x + 1, y + 1)

 
C++ implementation –
 

Download   Run Code

Output:

‘C'(2, 2) ‘O'(1, 1) ‘D'(0, 0) ‘E'(0, 1)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 0) ‘E'(3, 0)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(1, 2)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(3, 0)
‘C'(2, 2) ‘O'(1, 1) ‘D'(2, 1) ‘E'(3, 2)
‘C'(2, 2) ‘O'(2, 3) ‘D'(2, 4) ‘E'(1, 4)
‘C'(2, 2) ‘O'(2, 3) ‘D'(3, 3) ‘E'(3, 2)
‘C'(2, 2) ‘O'(2, 3) ‘D'(3, 3) ‘E'(4, 3)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz