剑指Offer-12：矩阵中的路径_剑指 offer 12. 矩阵中的路径c++-CSDN博客

本文链接：https://blog.csdn.net/Koala_Tree/article/details/78912174

题目：

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例子：

例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

问题解析：

将矩阵以二维数组的形式处理，属于在有边界的范围内查找路径的问题。

链接：

剑指Offer（第2版）：P89

思路标签：

算法：回溯法、递归

解答：

1. C++

回溯法适合于多步骤组成的问题，并且每一步中都有多个选项。
通常回溯算法适合用递归来实现。
思想比较简单，需要注意边界条件的处理。见代码吧。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == nullptr || rows <= 0 || cols <= 0 || str == nullptr) return false;

        bool* visited = new bool[rows*cols];
        //将申请的visited内存均初始化为0
        memset(visited, 0, rows*cols);

        int pathLength = 0;
        for(int row=0; row<rows; ++row){
            for(int col=0; col<cols; ++col){
                //多加一个if判断的原因是为了在没有找到的情况下，将visited内存删除，如果找到，保留可以对visited内存访问。
                if(hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited))
                    return true;
            }
        }

        delete[] visited;
        return false;
    }

    bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited){
        \\找到所有的str中元素的标志
        if(str[pathLength] == '\0') return true;

        bool hasPath = false;
        if(row >= 0 && col >= 0 && row < rows && col < cols && matrix[row*cols + col] == str[pathLength] && !visited[row*cols + col]){
            ++pathLength;
            visited[row*cols + col] = true;

            hasPath = hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited) 
            || hasPathCore(matrix, rows, cols, row-1, col, str, pathLength, visited) 
            ||hasPathCore(matrix, rows, cols, row, col+1, str, pathLength, visited) 
            || hasPathCore(matrix, rows, cols, row+1, col, str, pathLength, visited);

            if(!hasPath){
                --pathLength;
                visited[row*cols + col] = false;
            }
        }

        return hasPath;
    }
};