media.net recruitment challenge-1

  1. 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?

Use DFS in the matrix and mark cells as visited.

@aniketsanadhya

can you post another problem also if you remember.