int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
class Solution {
public:
    bool solve(vector<vector<char>>& arr,string s,vector<vector<int>>& vis,int i,int x,int y,int n,int m)
    {
        if(i==s.size())
            return true;
        bool flag = false;
        for(int j=0;j<4;j++)
        {
            int x1 = x+dx[j];
            int y1 = y+dy[j];
            if(x1>=0&&x1<n&&y1>=0&&y1<m&&!vis[x1][y1]&&arr[x1][y1]==s[i])
            {
                vis[x1][y1]=1;
                flag|=solve(arr,s,vis,i+1,x1,y1,n,m);
                vis[x1][y1]=0;
                if(flag)
                    return true;
            }
        }
        return flag;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();
        vector<vector<int>> vis(n,vector<int>(m,0));
        // memset(vis,0,sizeof(vis));
        int f=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==word[0])
                {

                    vis[i][j]=1;
                    if(solve(board,word,vis,1,i,j,n,m))
                    {
                        return true;
                    }
                    vis[i][j]=0;
                }
            }
        }
        return false;
    }
};