Question

How to search for a word in a grid of characters with C#

Answer 1

using System;

// use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched. 

class WordSearch
{
    static bool DFS(char[,] grid, bool[,] visited,
                    int r, int c, string word, int index)
    {
        if (index == word.Length)
            return true;

        int rows = grid.GetLength(0);
        int cols = grid.GetLength(1);

        if (r < 0 || c < 0 || r >= rows || c >= cols)
            return false;

        if (visited[r, c])
            return false;

        if (grid[r, c] != word[index])
            return false;

        visited[r, c] = true;

        bool found =
            DFS(grid, visited, r + 1, c, word, index + 1) ||
            DFS(grid, visited, r - 1, c, word, index + 1) ||
            DFS(grid, visited, r, c + 1, word, index + 1) ||
            DFS(grid, visited, r, c - 1, word, index + 1);

        visited[r, c] = false;
        
        return found;
    }

    static bool WordExist(char[,] grid, string word)
    {
        int rows = grid.GetLength(0);
        int cols = grid.GetLength(1);

        bool[,] visited = new bool[rows, cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (DFS(grid, visited, r, c, word, 0))
                    return true;
            }
        }
        return false;
    }

    static void Main()
    {
        char[,] grid = {
            { 'a', 'b', 'c', 'e' },
            { 's', 'f', 'c', 's' },
            { 'a', 'd', 'e', 'e' }
        };

        string word = "see";

        bool result = WordExist(grid, word);

        Console.WriteLine(result ? 1 : 0);
    }
}


/*
run:

1

*/

 

70+ SQL courses for beginners and professionals