- Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. You are allowed to move in all 8 directions from a cell.
Examples
Input:
First line: Number of matrices (Example: 2)
Then for each matrix
Input line 1: Number of rows and columns of the matrix below (eg: 3 3)
Input each row of matrix in each line.
eg:
a c d
h b e
i g f
Input then starting point (eg: e)
Output: 5
If starting point is ‘e’, then longest path with consecutive characters is “e f g h i”.
Input: mat[R][C] = {
{b, e, f},
{h, d, a},
{i, c, a}
}
Starting Point = ‘b’
Output: 1
‘c’ is not present in all adjacent cells of ‘b’
Input
The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 2 numbers separated by a space, N and M, followed by an N x M matrix, with each character space separated. The last part of the test case contains a character to use as the starting point in the matrix.
Output
The output consists of T numbers separated by new lines, indicating the length of the longest path of the respective test case with the given starting letter.
Constraints
1 = T = 100
1 = N = 100
1 = M = 100
Sample Input
2
4 4
a c d e
h b a t
i g f g
j s e f
f
3 3
a b c
d e f
g h i
a
Sample Output
5
3
Explanation
In the first test there are two possible starting point for f with the longest path being f(3,3)->g(3,2)->h(2,1)->i(3,1)->j(4,1)
In the second test there is only one possible starting point for a with the longest path being a(1,1)->b(1,2)->c(1,3)
How do we solve this problem?