Question

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

Answer 1

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

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

bool dfs(char grid[3][4], int rows, int cols,
         int r, int c, const char *word, int index, bool visited[3][4]) 
{
    if (index == strlen(word))
        return true;

    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, rows, cols, r + 1, c, word, index + 1, visited) ||
        dfs(grid, rows, cols, r - 1, c, word, index + 1, visited) ||
        dfs(grid, rows, cols, r, c + 1, word, index + 1, visited) ||
        dfs(grid, rows, cols, r, c - 1, word, index + 1, visited);

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

bool wordExist(char grid[3][4], const char *word) {
    int rows = 3, cols = 4;
    bool visited[3][4] = { false };

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

int main() {
    char grid[3][4] = {
        {'a', 'b', 'c', 'e'},
        {'s', 'f', 'c', 's'},
        {'a', 'd', 'e', 'e'}
    };

    const char *word = "see";

    bool result = wordExist(grid, word);

    printf("%d\n", result);  // prints 1 if found, 0 if not

    return 0;
}



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals