给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
用深度优先遍历DFS的思想，构造一个递归函数dfs。传递矩阵信息、某个格子的位置(x,y)，以及要匹配的单词word和匹配开始字符位置pos。即从mat[x][y] 寻找是否有word[pos]往后的单词，存在则匹配成功，返回true。
因为格子不能重复使用，所以要建立一个visit[m][n]的数组，记录格子是否被用过。
dfs函数介绍：
1、进来先判断mat[x][y] 是否等于 word[pos] ，visit[x][y] 是否等于1？不相等或者该格子被用过则直接返回false;
2、单个字母匹配成功，再判断是否是最后一个字符，是的话返回true,找到了这个单词。
3、还不是最后一个单词，先将visit[x][y] = 1(表明用了这个格子）。接下来要向四个方向查找后面的字符，遍历上下左右四个格子，递归调用dfs函数查找，传递的参数中，(x,y)变为新格子的位置，pos= pos+ 1（从下一个字母开始匹配）。
4、如果四个方向上，有返回true的话，直接返回true。若4个方向都返回false,都没找到，则应回溯。将本格子visit[x][y] = 0;再返回false即可。
//上下左右四个方向
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
//递归查找
bool dfs(char** board,int** visit,int m,int n,int x,int y,int pos,char* word,int len){
if(board[x][y] != word[pos] || visit[x][y] == 1)
return false;
if(pos == (len - 1))
return true;
visit[x][y] = 1;
int new_x,new_y;
for(int k = 0;k<4;k++){
new_x = x + dx[k];
new_y = y + dy[k];
if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n)
continue;
else
if(dfs(board,visit,m,n,new_x,new_y,pos+1,word,len))
return true;
}
visit[x][y] = 0;
return false;
}
bool exist(char** board, int boardSize, int* boardColSize, char * word){
int m = boardSize,n = boardColSize[0];
int len = strlen(word);
if(len == 0)
return true;
//visit 标记是否被访问过 初始化为0
int** visit = malloc(sizeof(int*) * m);
for(int k = 0;k<m;k++){
visit[k] = malloc(sizeof(int)*n);
for(int t = 0;t<n;t++)
visit[k][t] = 0;
}
for(int i =0;i<m;i++)
for(int j =0;j<n;j++){
if(board[i][j] != word[0])
continue;
else
if(dfs(board,visit,m,n,i,j,0,word,len))
return true;
}
return false;
}运行结果如下：
