1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//确定方向
int dx[] = new int[]{-1,0,1,0};
int dy[] = new int[]{0,1,0,-1};
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,0,i,j)) return true;
        }
    }
    return false;
}
public boolean dfs(char[][] board,String word,int idx,int x,int y){
    if(word.charAt(idx) != board[x][y]){
        return false;
    }
    if(idx == word.length() - 1){
        return true;
    }
    //把走过的节点标为 "."
    char tem = board[x][y];
    board[x][y] = '.';
    for(int i = 0;i < 4;i++){
        int nx = x + dx[i],ny = y + dy[i];
        if(nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length || board[nx][ny] == '.'){
            continue; //判断另一个方向个节点是否满足
        }
        if(dfs(board,word,idx + 1,nx,ny)){
            return true;
        }
    }
    //以上均不满足，回退
    board[x][y] = tem;
    return false;
}