Problem Statement
Find a word in character matrix if only moves allowed are left, right, up and down. Suppose a given matrix is as following.
A | S | O | P |
B | T | O | P |
P | O | T | R |
In above matrix if we are allowed to move left, right, up and down from any cell some of the valid words could be following.
STOP
A | S | O | P |
B | T | O | P |
P | O | T | R |
SOP
A | S | O | P |
B | T | O | P |
P | O | T | R |
POT
A | S | O | P |
B | T | O | P |
P | O | T | R |
We are given with matrix and the list of words, we have to find if words are present in matrix or not.
Solution
To solve this we need an additional matrix to track the visited cells once a cell is visited we do not go back to same cell. We need to start with each cell to and we go in all possible direction to find exact match character by character.
This is a backtracking problem where we try all possible permutations, once a invalid move is found we revert the visited cell to its original state. It will be easier to look into code and understand the solution.
static int[,] SearchWord(char[,] matrix, string word) { // Additional matrix to track solution and visited nodes int[,] solution = new int[matrix.GetLength(0), matrix.GetLength(1)]; // i, j to start with each cell in order to find solution until one solution is found for (int i = 0; i < matrix.GetLength(0); i++) { for (int j = 0; j < matrix.GetLength(1); j++) { var isFound = Search(matrix, solution, word, i, j, 0); if(isFound) return solution; } } return solution; }
Search method start the search from i'th row and j'th column in the matrix and returns true if word is found. We will write a method which returns valid moves when control is at cell(i'th row and j'th column).
// m and n are row and column count in matrix // row and column are current cell position in matrix
static List<(int, int)> GetValidMoves(int m, int n, int row, int column) { List<(int, int)> possibleMoves = new List<(int, int)>(); // Can go UP if(row - 1 >= 0) { possibleMoves.Add((row - 1, column)); } // Can go DOWN if (row + 1 < m) { possibleMoves.Add((row + 1, column)); } //Can go LEFT if (column - 1 >= 0) { possibleMoves.Add((row, column - 1)); } // Can go RIGHT if (column + 1 < n) { possibleMoves.Add((row, column + 1)); } return possibleMoves; }
Above methods returns list of all possible moves from a cell, suppose if current cell is (0, 0) then control can move only Right(0, 1) and Down(1,0). Diagonal(1, 1) is not allowed and (-1, 0), (0, -1), (-1, -1) are not valid cells in matrix. So in that case above method will return [(0,1), (1, 0)].
static bool Search(char[,] matrix, int[,] solution, string word, int row, int column, int pathLength) { // All characters are found, return true if (word.Length == pathLength) { return true; } // If this marix cell is already visited or does not contain required character if (solution[row, column] != 0 || matrix[row, column] != word[pathLength]) { return false; } // pathLength is incremental so we can match next character if last one is found pathLength++; solution[row, column] = pathLength; var validMoves = GetValidMoves(matrix.GetLength(0), matrix.GetLength(1), row, column); foreach (var (x, y) in validMoves) { if (Search(matrix, solution, word, x, y, pathLength)) return true; } // backtrack solution[row, column] = 0; return false; }
Below are break conditions
- If all characters are found(word.Length == pathLength)
- If matrix cell is already visited
- If current cell does not contain desired character
If no further valid moves found we backtrack the solution so we set solution array cell back to zero.
Lets run above code:
static void Main(string[] args) { char[,] matrix = new char[,] { { 'A', 'S', 'O', 'P' }, { 'B', 'T', 'O', 'P' }, { 'P', 'O', 'T', 'R' } }; List<string> words = new List<string>() { "STOP", "SOP", "POT" }; Console.WriteLine("Given Matrix:"); for (int i = 0; i < matrix.GetLength(0); i++) { for (int j = 0; j < matrix.GetLength(1); j++) { Console.Write(matrix[i, j] + " "); } Console.WriteLine(); } Console.WriteLine(); foreach (string word in words) { // Find solution var solution = SearchWord(matrix, word); Console.WriteLine($"Solution for {word} is"); for (int i = 0; i < solution.GetLength(0); i++) { for (int j = 0; j < solution.GetLength(1); j++) { Console.Write(solution[i, j] + " "); } Console.WriteLine(); } Console.WriteLine(); } }
Output

Comments: