class Solution {
public:
    
    int ** visited;
    
    const char * str;
    
    int row = 0 , col = 0;
    
    int nx[4] = {-1,1,0,0};
    int ny[4] = {0,0,-1,1};
    
    bool issafe( int x, int y ) {
        if( x >=  0 && x < row && y >= 0 && y < col ) {
            return true;
        }
        return false;
    }
    
    bool check( vector< vector<char> > &board, int i, int j, const char * str ) {
        
        if( visited[i][j] == 1 ) {
            return false;
        }
        
        if( board[i][j] == *str && *(str+1) == '\0' ) {
            return true;
        }
        
        visited[i][j] = 1;
        
        if( board[i][j] == *str ) {
            for( int k = 0 ; k < 4 ; k++ ) {
                int newx = i + nx[k];
                int newy = j + ny[k];
                
                if( issafe(newx,newy) ) {
                    bool temp = check(board,newx,newy,str+1);
                    if( temp == true ) {
                        return true;
                    }
                }
            }
        }
        
        visited[i][j] = 0;
        
        return false;
        
    }
    
    bool exist(vector<vector<char> > &board, string word) {
        
        str = word.c_str();
        row = board.size();
        col = board[0].size();
        
        
        visited = (int **) calloc(sizeof(int *) , row);
        for( int i = 0 ; i < row ; i++ ) {
            visited[i] = (int *) calloc(sizeof(int) , col);
        }
        
        for( int i = 0 ; i  < row ; i++ ) {
            for( int j = 0 ; j < col ; j++ ) {
                if( board[i][j] == str[0] ) {
                    bool ans = check(board,i,j,str);
                    if( ans == true ) {
                        return true;
                    }
                }
            }
        }
        
        return false;
        
    }
};