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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <iostream> using namespace std; // Size of given matrix is M x N #define M 5 #define N 5 // Below arrays details all 8 possible movements int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; // check whether cell (x, y) is valid or not bool isValid(int x, int y) { return (x >= 0 && x < M && y >= 0 && y < N); } // Find length of longest path in the matrix mat[][] with consecutive characters // The path should continue from the previous character // Here (i, j) denotes the coordinates of the current cell int findMaxLength(char mat[][N], int x, int y, char previous) { // base case: return length 0 if current cell (x, y) is invalid or // current character is not consecutive to the previous character if (!isValid(x, y) || previous + 1 != mat[x][y]) return 0; // stores the length of longest path int max_length = 0; // recurse for all 8 adjacent cells from current cell for (int k = 0; k < 8; k++) { // visit position (x + row[k], y + col[k]) and find the // maximum length from that path int len = findMaxLength(mat, x + row[k], y + col[k], mat[x][y]); // update the length of longest path if required max_length = max(max_length, 1 + len); } return max_length; } // Find length of longest path in the matrix with consecutive characters int findMaxLength(char mat[][N], char ch) { // stores the length of longest path int max_length = 0; // traverse the matrix for (int x = 0; x < M; x++) { for (int y = 0; y < N; y++) { // start from the current cell if its value matches with // the given character if (mat[x][y] == ch) { // recurse for all 8 adjacent cells from current cell for (int k = 0; k < 8; k++) { // visit position (x + row[k], y + col[k]) and find the // maximum length from that path int len = findMaxLength(mat, x + row[k], y + col[k], ch); // update the length of longest path if required max_length = max(max_length, 1 + len); } } } } return max_length; } int main() { // input matrix char mat[][N] = { { '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' } }; // starting character char ch = 'C'; cout << "The length of longest path with consecutive characters " << "starting from character " << ch << " is " << findMaxLength(mat, ch) << endl; return 0; } |

`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