题目：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。 例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 [["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]] 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后， 路径不能再次进入这个格子。 示例 1： 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true 示例 2： 输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false 提示： 1 <= board.length <= 200 1 <= board[i].length <= 200思路： 对于这个题目，首先看到就会想DFS（也就是所谓回溯思想） 思路上：对于每一个字母从它开始向四周开始搜索，如果搜索到的字符拼接起来与目标字符串前面一致，那么就继续向四周搜索，如果不一致，就返回！从上一层的另一个方向继续搜索； 如果4个方向都搜索完也没有找到，记得将搜索过程的记录清除，并返回；
例如：这个矩阵，目标为：“bfce” 实现过程中的难点： 对于走过的路径，我们需要一个同样大小的二维数组来记录是否走过，为了节省内存空间，我们使用引用传递这个数组，这就意味着在当前路径未找到目标字符时（四个方向搜索结束未找到）：我们需要将当前位置恢复为未搜索状态（true） 也就是下面的visited数组；并将添加进来的字符删除！（str.pop_back()）
另一个难点： 在当前DFS函数中，末尾处也就是四个方向搜索结束后，我们并不知道是否搜索到完整的字符串并层层返回，因此需要在第一个难点（删除踪迹）之前判断：当前是否已经找到目标！如果找到则不需要删除字符，直接返回就ok了，层层返回之后，在主函数exist中会判断是否已经找到！
代码：
class Solution { public: bool exist(vector<vector<char>>& board, string word) { if(board.size()==0) return false; int count = 0; for(int i = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++){ if(board[i][j] == word[0]){ vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), true)); string ret_str = ""; DFS(board, word, ret_str,i, j, count,visited); if(ret_str == word) return true; ret_str = ""; } } } return false; } void DFS(vector<vector<char>>& board, string word, string& ret_str, int i,int j, int count, vector<vector<bool>>& visited) { ret_str += board[i][j]; visited[i][j] = false; count++; if(ret_str == word) return; // cout << "in: " << ret_str << endl; if(i-1 >=0 && board[i-1][j] == word[count] && visited[i-1][j] == true) DFS(board, word, ret_str,i-1, j, count,visited); if(i+1 < board.size() && board[i+1][j] == word[count] && visited[i+1][j] == true) DFS(board, word, ret_str,i+1, j, count,visited); if(j-1 >=0 && board[i][j-1] == word[count] && visited[i][j-1] == true) DFS(board, word, ret_str,i, j-1, count,visited); if(j+1 < board[0].size() && board[i][j+1] == word[count] && visited[i][j+1] == true) DFS(board, word, ret_str,i, j+1, count,visited); if(ret_str == word) return; visited[i][j] = true; ret_str.pop_back(); } };