给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.解法
这道题目可以使用回溯法来解决，这里提几个关键的地方。
line29 重置为 false，这是回溯法的关键，即将状态回滚回到递归前的状态。
line3 方向数组，配合 line22 可以将代码量压缩很多，而且逻辑关系十分清晰。
class Solution {
public:
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
vector<vector<bool>> visited;
bool judge(int x,int y){
if(x>=0 && y>=0 && y<n && x<m){
return true;
}
return false;
}
bool recursion(const vector<vector<char>>& board,int startx,int starty,const string& word,int index){
if(index==word.size()-1){
return word[index]==board[startx][starty];
}
if(board[startx][starty]==word[index]){
visited[startx][starty] = true;
for(int i=0;i<4;i++){
int newx = startx+d[i][0];
int newy = starty+d[i][1];
if(judge(newx,newy) && !visited[newx][newy] && recursion(board,newx,newy,word,index+1) ){
return true;
}
}
visited[startx][starty] = false;
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
m=board.size();
n=board[0].size();
visited = vector<vector<bool>>(m,vector<bool>(n,false));
// if(my==0 ) return false;
for ( int i=0;i<m;i++){
for (int j=0;j<n;j++){
if(recursion(board,i,j,word,0)) return true;
}
}
return false;
}
};
