class Solution {
public:

    bool dfs(vector<vector<char>>& board, string& word, int i,int j,int size)
    {
        if(i>=board.size()||j>=board[0].size()||i<0||j<0||size>=word.size()||word[size]!=board[i][j])
        {
            return false;
        }
        if(word[size] == board[i][j] && word.size()-1 == size)
        {
            return true;
        }
        char temp = board[i][j];
        board[i][j] = '0';
        bool flag = dfs(board,word,i+1,j,size+1) || dfs(board,word,i-1,j,size+1) || 
        dfs(board,word,i,j+1,size+1) || dfs(board,word,i,j-1,size+1);
        board[i][j] = temp;
        return flag;

    }
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0)
        {
            return false;
        }
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(dfs(board,word,i,j,0))
                {
                    return true;
                }
            }
        }
        return false;
    }
};