给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 回溯法DFS
class Solution { char [][]board; int m; int n; int [][]dirs={{-1,0},{1,0},{0,-1},{0,1}}; boolean [][] visited; public boolean exist(char[][] board, String word) { this.board=board; m=board.length; n=board[0].length; visited=new boolean[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]==word.charAt(0)){ if(dfs(i,j,word,0)){ return true; } } } } return false; } public boolean dfs(int x,int y,String word,int i){ if(i==word.length()-1){ return true; } visited[x][y]=true; for(int []dir:dirs){ int new_x=x+dir[0]; int new_y=y+dir[1]; //此if条件可以写成一个函数，增加可读性。 if(new_x>=0&&new_x<m&&new_y>=0&&new_y<n&&word.charAt(i+1)==board[new_x][new_y]&&!visited[new_x][new_y]){ if(dfs(new_x,new_y,word,i+1)){ return true; } } } visited[x][y]=false; return false; } }