1. Two characters are said to be adjacent if they share a side or corner i.e. for a cell inside the matrix have 8 adjacent cells (if they exist). 2. One character in the matrix will not be considered twice for forming a word. 3. All the characters in the matrix and words consist only of uppercase English alphabets only.
The first line of the input contains three space-separated integers 'N', 'M', and 'Q' denoting the number of rows in the matrix, the number of columns in the matrix, and the number of queries respectively. The following 'N' lines contain 'M' characters each, denoting the characters in i’th row of the matrix. The following 'Q' lines contain a string ‘W’ each, denoting the word to be searched in the matrix.
For each query print a single line containing ‘1’ if the word is present in the matrix and ‘0’ if the word is not present in the matrix in a separate line. For more clarity refer to sample test cases. The output of each query will be printed in a separate line.
You don't have to print anything, it has already been taken care of. Just Implement the given function.
1 <= N * M <= 12 1 <= Q <= 100 1 <= |W| <= 20
Let’s say we have a matrix as follows:
And words that need to be searched are ZOOM, ZOO, MOOD.
So trie for these words will look like this:-
Following the above algo,rithm we just need to pick those cells in the matrix where the character is Z or M. Then use that cell as the starting position and start looking for the next character in the trie, from the neighbour of that cell in the matrix.
In the given matrix we start at location (1, 1) where Z is located, then we just need to go towards that direction where the next character will be O and that is an unvisited cell only. As there is only one sub-trie of Z. By which we can reach location (1, 2) or (2, 1). While moving to these locations we mark (1, 1) as visited. Again start the search from that point.
Also while moving to any new cell, first mark the queries at index present in wordEndingHere list present in that trie node.
This way, queries like ZOO and ZOOM can be searched simultaneously.