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