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.

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

SOP

POT

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

1. If all characters are found(word.Length == pathLength)
2. If matrix cell is already visited
3. 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