单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
] 给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
思路：回溯算法，返回false的条件是探索到达了边界，已经探索过了，探索的字母与给定字符串的字符不相等。
探索是向上下左右探索，因此有四个回溯（bcakTrace()）。
class Solution {
public boolean exist(char[][] board, String word) {
int rows=board.length; //长
int cols=board[0].length;
boolean res=false;
boolean[][] mark=new boolean[rows][cols];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(word.charAt(0)==board[i][j]){ //先找到字符串的起点
res=backTrace(0,word,board,i,j ,mark );
if(res==true)return true;
}
}
}
return false;
}
public boolean backTrace(int index,String word,char[][] board,int row,int col,boolean[][] mark){
if(index==word.length())return true; //回溯的边界条件
if(row>=board.length||row<0||col>=board[0].length||col<0)return false;
if(mark[row][col]==true||word.charAt(index)!=board[row][col])return false;
mark[row][col]=true;
if(backTrace(index+1,word,board,row+1,col,mark)||
backTrace(index+1,word,board,row-1,col,mark)||
backTrace(index+1,word,board,row,col+1,mark)||
backTrace(index+1,word,board,row,col-1,mark))
return true;
mark[row][col]=false; //每次探索至边界，不成立时，都要将标记清除
return false;
}
}