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(dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    public static boolean dfs(char[][] board, String word, int i, int j, int k) {
        
        int m = board.length-1;
        int n = board[0].length-1;
        
        //如果i或j已经超出边界，或者该位置的值和word的第一个字符不符，直接返回false
        if(i<0 || i>m || j<0 || j>n || board[i][j]!=word.charAt(k)) {
            return false;
        }
 
        //如果把word都遍历完了，说明合适
        if(k >= word.length()-1) {
            return true;
        }
        
        //先把这个位置置为其他字符，防止重复访问
        board[i][j] = '0';
        
        //向上下左右找（已经将原位置为空，不用担心又找回原位），找到就返回true
        boolean result = dfs(board, word, i-1, j, k+1) || dfs(board, word, i+1, j, k+1) ||
                         dfs(board, word, i, j-1, k+1) || dfs(board, word, i, j+1, k+1);
        
        //把置空的位置恢复
        board[i][j] = word.charAt(k);
        
        return result;
    }
}