《剑指offer》c++版本 12. 矩阵中的路径

如题，牛客网上题目没有图示，下图是从原书中截图得到的。

本题就是从数组中按照指定方向查找字符序列，典型的回溯行为，找到当前字符，继续查找该字符上下左右四个方向，找不到，返回上一个字符，重新查找。题目要求，路径中不能访问同一个字符，可以创建一个等大小的bool二维数组，记录已访问的点，每次访问一个点，置标志位，注意。如果该点的后一个结点不符合，再返回上一个节点前，需要去掉该标志位。

使用递归进行回溯处理即可，注意特殊情况处理，例如，字符串数组为空或者给定的字符串为空等。

下面是本题c++代码，在牛客网上的剑指offer板块验证完成，仅供参考：

//递归查找路径，找到直接返回，找不到顺时针换方向查找 //查找的时候，将访问的结点置位。 //特殊情况：str为空或者字符数组为空。 class Solution { public:bool searchPath(char* matrix, int rows, int cols, char* str, int prow, int pcol, vector<vector<bool>> &visited){char *pChar = str;//如果已经到了字符串末尾，则返回trueif (*pChar == '\0')return true;//判断是否超出边界if (prow < 0 || prow >= rows || pcol < 0 || pcol >= cols)return false;cout<<"["<<prow<<"]["<<pcol<<"]"<<endl;//判断是否该点已经访问过if (visited[prow][pcol])return false;//判断该点是否为所需字符if (matrix[prow*cols+pcol] == *pChar){//设置标志位，指向下一个字符visited[prow][pcol] = true;pChar++;//上if (searchPath(matrix, rows, cols, pChar, prow-1, pcol, visited))return true;//左if (searchPath(matrix, rows, cols, pChar, prow, pcol-1, visited))return true;//下if (searchPath(matrix, rows, cols, pChar, prow+1, pcol, visited))return true; //右if (searchPath(matrix, rows, cols, pChar, prow, pcol+1, visited))return true; //本点不符合，去掉置位visited[prow][pcol] = false;}elsereturn false;return false;}bool hasPath(char* matrix, int rows, int cols, char* str){int i = 0, j = 0;vector<vector<bool>> visited(rows, vector<bool>(cols, false)), &rVisited = visited;//特殊情况处理if (matrix == nullptr || str == nullptr || (rows == 0 && cols == 0))return false;//搜索路径for (; i < rows; i++){for (j = 0; j < cols; j++){if (matrix[i*cols+j] == *str && searchPath(matrix, rows, cols, str, i, j, rVisited))return true;}}return false;} };

=============================================================================================

Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。

总结

以上是生活随笔为你收集整理的《剑指offer》c++版本 12. 矩阵中的路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。