class Solution {
    boolean[][] vis;
    
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        vis = new boolean[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, i, j, word, 0)) return true;
            }
        }

        return false;
    }

    boolean dfs(char[][] board, int x, int y, String word, int ind){
        int m = board.length, n = board[0].length;
        if(x < 0 || x >= m || y < 0 || y >= n || word.charAt(ind) != board[x][y] || vis[x][y]) return false;
        if(ind == word.length() - 1) return true;

        vis[x][y] = true;
        if(dfs(board, x + 1, y, word, ind + 1)) return true;
        if(dfs(board, x, y + 1, word, ind + 1)) return true;
        if(dfs(board, x - 1, y, word, ind + 1)) return true;
        if(dfs(board, x, y - 1, word, ind + 1)) return true;
        vis[x][y] = false;


        return false;
    }
}