Grid and alphabets

Amanada, a school kid, is learning English alphabets. Her teacher devised a small game to make the task fun. A grid of ‘m’ rows and ‘n’ columns is filled with English alphabets. She needs to search English words in this grid by moving one step at a time in any of the adjacent grid cells.

A grid of alphabets and a set of English words are given. Amanda can start from anywhere in the grid and can move in any of the 8 adjacent grid cells, one step at a time. Each grid cell can only be used once.

Examples:

Input:
3 3 1 
a b c
d e f
g h i
abc
Output:
True

Input:
3 3 1
a b c
d e f
g h i
efgh

Output:
False

Explanation:
This problem is implementation of dfs algorithm in a m*n matrix. In this we have to first locate the first character of the word in the grid and make that position as root and then start the dfs.

We have Eight neighbours to explore for every node. When the word is matched return 1.

// Following is the implementation of above problem

#include<bits/stdc++.h>
using namespace std;

// all possible directions
int dx[] = {-1 , 0 , 1 , 1 , 1 , 0 , -1 , -1};
int dy[] = {1 , 1 , 1 , 0 , -1 , -1 , -1 , 0};
int len;
int vis[1000][1000];
char grid[1000][1000];

int solve(int r , int c , int m , int n , int pos, string word) {

    // mark the current position as visited
    vis[r][c] = 1;
    
    if(pos == len)// if word is found, then return
    {
        return 1;
    }
    
    for(int dir = 0; dir < 8; dir++) 
    {
        int curx = r + dx[dir];
        int cury = c + dy[dir];
        
        if(curx >= 0 && curx < m && cury >= 0 && cury < n && !vis[curx][cury] && grid[curx][cury] == word[pos]) {
            if(solve(curx , cury , m , n , pos + 1, word) ) {
                return 1;
            }
        }
    }
// mark it unvisited so that it can be used by other states
    vis[r][c] = 0;
    return 0;
}

int findWord (int m, int n, string word)
{
    memset(vis , 0 , sizeof vis);
    
    len=word.size();
    
// look for the first character in the grid and start the dfs
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j] == word[0]) {
                if(solve(i , j , m , n , 1, word) ) {
                 return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int m,n,q;
    
    cin>>m>>n>>q;
    
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>grid[i][j];
        }
    }
    
    
    string word;

    while(q--)
    {
        cin>>word;
        
        if(findWord(m,n,word))// returns whether the word is present or not
            cout<<"True\n";
        else
            cout<<"False\n";
    }
}