1#include <iostream>
2#include <vector>
3using namespace std;
4
5bool isWordExist(vector<vector<char>>& grid, string word, int row, int col, int index) {
6    int n = grid.size();
7    int m = grid[0].size();
8
9    // Base cases
10    if (index == word.size()) {
11        return true; // Word found
12    }
13
14    if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] != word[index]) {
15        return false; // Current cell doesn't match the character
16    }
17
18    // Mark the current cell as visited
19    char temp = grid[row][col];
20    grid[row][col] = '#';
21
22    // Explore the neighboring cells
23    bool found = isWordExist(grid, word, row, col + 1, index + 1) ||
24                 isWordExist(grid, word, row, col - 1, index + 1) ||
25                 isWordExist(grid, word, row + 1, col, index + 1) ||
26                 isWordExist(grid, word, row - 1, col, index + 1);
27
28    // Restore the cell
29    grid[row][col] = temp;
30
31    return found;
32}
33
34bool wordSearch(vector<vector<char>>& grid, string word) {
35    int n = grid.size();
36    int m = grid[0].size();
37
38    // Iterate over each cell in the grid
39    for (int i = 0; i < n; i++) {
40        for (int j = 0; j < m; j++) {
41            if (grid[i][j] == word[0]) {
42                // Check if the word exists starting from this cell
43                if (isWordExist(grid, word, i, j, 0)) {
44                    return true; // Word found
45                }
46            }
47        }
48    }
49
50    return false; // Word not found
51}
52
53int main() {
54    // Grid representing the word search puzzle
55    vector<vector<char>> grid = {
56        {'A', 'B', 'C'},
57        {'F', 'I', 'N'},
58        {'T', 'O', 'R'}
59    };
60
61    // Word to be searched
62    string word = "BIT";
63
64    // Check if the word exists in the grid
65    bool exists = wordSearch(grid, word);
66
67    // Print the result
68    if (exists) {
69        cout << "The word \"" << word << "\" exists in the grid." << endl;
70    } else {
71        cout << "The word \"" << word << "\" does not exist in the grid." << endl;
72    }
73
74    return 0;
75}