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;
}
|