对于这道题。。我也无话可说了。。无奈了。。。
最开始就是用dfs做，写出来之后怎么测试都是time limit exceeded。。。。上网看大家的解决方法都一样啊，都是上下左右检查一遍。。。。我这个郁闷啊
但是后来我检查出我的代码有个严重的问题。。用dfs在回溯的时候，我们没有把这个点的visit标记回复为false。。因此这里一定要注意
如果在dfs时候将原来的状态做了改变，一定要在回溯结束的时候将状态改变回来。。。。
就像做subset时候一样，用tmp保留当前的状态，如果不满足条件回溯的时候，一样要将这一轮添加进去的元素删除掉！！！！
但即使发现这个问题，依然是time limit exceeded。。。这个郁闷啊。。我和网上大家做法一样，为啥我就不行。。
后来我终于发现了。。。
我最开始想的是，每次遇到一个和word首字符一样的字符就开始做dfs，用visited标记是否访问过。那么下一次做的时候我应该是这个visited数组清空掉。。我很聪明的在每次循环里重新new出一个boolean数组。。。。当数据很大时，这个数据就很大，就要很多时间。。。。。。所以发生了超时。。
结合我上面提到的dfs很关键的一点，每次dfs结束之后，visited会自己就回复到最初始的状态！！！！！！
1 public static boolean exist(char[][] board, String word) { 2 if (board == null) return false; 3 if (word.length() == 0) return true; 4 int row = board.length; 5 if (row == 0) return false; 6 int col = board[0].length; 7 if (col == 0) return false; 8 boolean visited[][] = new boolean[board.length][board[0].length]; 9 for (int i=0; i<row; i++) { 10 for (int j=0; j<col; j++) { 11 // boolean visited[][] = new boolean[board.length][board[0].length]; 12 if (dfs(board, i, j, word, 0, visited)) 13 return true; 14 } 15 } 16 return false; 17 } 18 19 public static boolean dfs(char[][] board, int i, int j, String word, int position, boolean visited[][]) { 20 if (i<0 || i>=board.length || j<0 || j>=board[0].length) return false; 21 if (visited[i][j] || board[i][j] != word.charAt(position)) return false; 22 if (position == word.length()-1) return true; 23 24 visited[i][j] = true; 25 boolean result = dfs(board, i-1, j, word, position+1, visited) || 26 dfs(board, i, j+1, word, position+1, visited) || 27 dfs(board, i+1, j, word, position+1, visited) || 28 dfs(board, i, j-1, word, position+1, visited); 29 visited[i][j] = false; 30 return result; 31 }
。。。