1+ package Algorithms .dfs ;
2+
3+ public class Exist {
4+ public boolean exist (char [][]board ,String word ) {
5+ if (board ==null ||word ==null
6+ ||board .length ==0 ||board [0 ].length ==0 ) {
7+ return false ;
8+ }
9+
10+ int rows =board .length ;
11+ int cols =board [0 ].length ;
12+
13+ boolean [][]visit =new boolean [rows ][cols ];
14+
15+ // i means the index.
16+ for (int i =0 ;i <rows ;i ++) {
17+ for (int j =0 ;j <cols ;j ++) {
18+ // dfs all the characters in the matrix
19+ if (dfs (board ,i ,j ,word ,0 ,visit )) {
20+ return true ;
21+ }
22+ }
23+ }
24+
25+ return false ;
26+ }
27+
28+ public boolean dfs (char [][]board ,int i ,int j ,String word ,int wordIndex ,boolean [][]visit ) {
29+ int rows =board .length ;
30+ int cols =board [0 ].length ;
31+
32+ int len =word .length ();
33+ if (wordIndex >=len ) {
34+ return true ;
35+ }
36+
37+ // the index is out of bound.
38+ if (i <0 ||i >=rows ||j <0 ||j >=cols ) {
39+ return false ;
40+ }
41+
42+ // the character is wrong.
43+ if (word .charAt (wordIndex ) !=board [i ][j ]) {
44+ return false ;
45+ }
46+
47+ // 不要访问访问过的节点
48+ if (visit [i ][j ] ==true ) {
49+ return false ;
50+ }
51+
52+ visit [i ][j ] =true ;
53+
54+ // 递归
55+ // move down
56+ if (dfs (board ,i +1 ,j ,word ,wordIndex +1 ,visit )) {
57+ return true ;
58+ }
59+
60+ // move up
61+ if (dfs (board ,i -1 ,j ,word ,wordIndex +1 ,visit )) {
62+ return true ;
63+ }
64+
65+ // move right
66+ if (dfs (board ,i ,j +1 ,word ,wordIndex +1 ,visit )) {
67+ return true ;
68+ }
69+
70+ // move left
71+ if (dfs (board ,i ,j -1 ,word ,wordIndex +1 ,visit )) {
72+ return true ;
73+ }
74+
75+ // 回溯
76+ visit [i ][j ] =false ;
77+ return false ;
78+ }
79+ }