Find length of longest path in the matrix with consecutive characters

Given a M x N matrix of characters, find the length of longest path in the matrix starting from a given character. All characters in the longest path should be increasing and consecutive to each other in alphabetical order.

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.

 
For example, consider below matrix of characters,


[ D, E, H, X, B ]
[ A, O, G, P, E ]
[ D, D, C, F, D ]
[ E, B, E, A, S ]
[ C, D, Y, E, N ]

The length of longest path with consecutive characters starting from character C is 6.

The longest path is:

C(2, 2) -> D(2, 1) -> E(3, 2) -> F(2, 3) -> G(1, 2) -> H(0, 2)
 

 
We can use DFS to solve this problem. The idea is to start from given starting character in the matrix and explore all eight paths possible and recursively find the length of longest 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.

row[] = { -1, -1, -1, 0, 0, 1, 1, 1 }
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)

 
The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

The length of longest path with consecutive characters starting from character C is 6

 
Note that we don’t need to keep track of cells involved in current path in an matrix, since the path is formed by consecutive characters which is strictly increasing and there won’t be any cycles in the output path.

 
The problem also exibits both optimal substructure and overlapping subproblems properties of dynamic programming. So we can save sub-problem solutions in memory rather than computing them again and again. The dynamic programming implementation is left as an exercise to the readers.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of