class Solution {
public:
    bool func(vector<vector<char>>& board,vector<vector<bool>> &vis,int i,int j,int k,string &word)
    {
        int m=board[0].size();
        int n=board.size();
        
        if(k==word.length())
            return true;
        
        if(i<0||i>=n)
            return false;
        
            if(j<0||j>=m)
            return false;
        
        if(board[i][j]!=word[k]||vis[i][j]==true)
            return false;
        
        
            vis[i][j]=true;
        
 bool t= func(board,vis,i,j+1,k+1,word)||func(board,vis,i,j-1,k+1,word)||
            func(board,vis,i+1,j,k+1,word)||func(board,vis,i-1,j,k+1,word);
            
            vis[i][j]=false;
        
            return t;
        
        
    }
    
    
    
    bool exist(vector<vector<char>>& board, string word)  {
     
        int n=board.size();
        int m=board[0].size();
       
        
        vector<vector<bool>> vis(n,vector<bool>(m,false));//
        
        bool t;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++){
                if(board[i][j] == word[0]){
                    t = func(board,vis,i,j,0,word);
                    
                    if(t)
                        return true;
                }
            }
        }
        
          return  false;   
   
        
    }
};