写在前面：
军训好累.......
题目：剑指 Offer 12. 矩阵中的路径 - 力扣（Leetcode）
题目的接口：
class Solution { public: bool exist(vector>& board, string word) { } };
解题思路：
这道题不算很难，一眼看过去，
一下就能想到这就是用深度优先搜索（DFS），
说人话其实就是全部递归遍历一遍就行，
与所需字符串对应，符合要求就递归下去，不符合就返回。
只要注意一下细节上的问题就行。（注意走回头路这种情况）
具体思路：
1. 遍历整个矩阵
2. 通过递归判断矩阵中的每一个字符是否能够串成题目要求的字符串
3. 如果匹配成功返回true，如果匹配失败则返回false。
代码：
class Solution { public: bool exist(vector>& board, string word) { //矩阵的长和宽 row = board.size(); col = board[0].size(); //遍历整个矩阵 for(int i = 0;i { for(int j = 0;j { //递归搜索是否存在与题目要求相同的字符串 if(dfs(board, word, i, j, 0)) { return true; } } } return false; } //可以建一个地方存放私有成员，方便我们访问 private: //初始化 int row, col; //递归函数的实现 // k 是用来做为字符串word的下标的 bool dfs(vector>& board, string word, int i, int j, int k) { //如果出现越界或者匹配失败，返回false if(i >= row || i < 0 || j >= col || j < 0 || board[i][j] != word[k]) { return false; } //如果目标字符已经匹配完了，返回true if(k == word.size() - 1) { return true; } //细节：为了防止“走回头路”这种情况发生，改变位置原字符 board[i][j] = '\0'; //四个角度递归搜索，不符合条件返回false，符合的继续递归 bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j - 1, k + 1); //搜素完后可以将原字符变回原样 board[i][j] = word[k]; //返回最后递归的结果 return res; } }; 过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
