class Solution {
    public boolean exist(char[][] board, String word) {
        int rows=board.length,cols=board[0].length;
        boolean[][] used=new boolean[rows][cols];
        //枚举所有起点
        for(int r=0;r<rows;r++){
            for(int c=0;c<cols;c++){
                if(dfs(board,used,r,c,word,0)){
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board,boolean[][] used,int r,int c,String word,int pos){
        //如果r和c越界，或者当前位置已经访问过，或者当前位置和目标不相同，就返回false
        if(r<0 || r>=board.length || c<0 || c>=board[0].length || used[r][c] || word.charAt(pos)!=board[r][c]) return false;
        //这里是当前位置和目标相同的情况，如果额外的，pos是最后一个，就说明找到了
        if(word.length()-1==pos) return true;
        used[r][c]=true;
        boolean ans=dfs(board,used,r-1,c,word,pos+1) || 
                    dfs(board,used,r+1,c,word,pos+1) || 
                    dfs(board,used,r,c-1,word,pos+1) || 
                    dfs(board,used,r,c+1,word,pos+1);
        used[r][c]=false;
        return ans;
    }
}