#include <queue>
using namespace std;

class Solution {
    vector<vector<bool> > visited;
public:
    bool dfs(vector<vector<char> >& board, int i, int j, string word, int depth) { 
        if(board[i][j] != word[depth])
            return false;
        if(depth >= (word.size() - 1))
            return true;       
        visited[i][j] = true;
        int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        for(int k=0; k<4; k++) { 
            int nx = i + dir[k][0];
            int ny = j + dir[k][1];
            if(nx >= 0 && nx < board.size() &&  
               ny >= 0 && ny < board[0].size() && !visited[nx][ny]) {
                if(dfs(board, nx, ny, word, depth+1))
                    return true;
            }
        }
        visited[i][j] = false;
        return false;
    }
    
    bool exist(vector<vector<char> >& board, string word) {
        if(board.size() == 0 || word.length() == 0)
            return false;
        visited = 
        vector<vector<bool> >(board.size(), vector<bool>(board[0].size(), false));
        for(int i=0; i < board.size(); i++) { 
            for(int j=0; j < board[0].size(); j++) { 
                if(dfs(board, i, j, word, 0))
                  return true;
            }
        }
        return false;
    }
};