class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(board[i][j] == word.charAt(0)) {
                    boolean value = existRec(board, word, j, i, new int[board.length][board[0].length], 0);
                    if(value)
                        return true;
                }
            }
        }
        return false;
    }
    
    public boolean existRec(char[][] board, String word, int x, int y, int[][] visited, int index) {
        if(index >= word.length())
            return true;
        
        if(x<0 || x>=board[0].length)
            return false;
        if(y<0 || y>=board.length)
            return false;
        
        if(visited[y][x] != 0)
            return false;
        if(board[y][x] != word.charAt(index))
            return false;
        
        visited[y][x] = 1;
        boolean bool = 
            existRec(board, word, x-1, y, visited, index+1) ||
            existRec(board, word, x+1, y, visited, index+1) ||
            existRec(board, word, x, y-1, visited, index+1) ||
            existRec(board, word, x, y+1, visited, index+1);
        
        visited[y][x] = 0;
        return bool;
    }
}