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

思路在书上和代码里面注释的很清楚

代码：

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

        bool *visited = new bool[rows*cols];//一维指针数组
        memset(visited, 0, rows * cols);//初始化指针数组
        int pathLength = 0;//定义初始路径长度
        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                if (hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited))
                {
                    return true;
                }
            }
        }
        delete[] visited;
        return false;
    }

    //hasPathCore(初始矩阵，矩阵行数，矩阵列数，行索引，列索引，待查询字符串，查找的路径长度，访问标志矩阵)
    bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int pathLength, bool* visited)
    {
        //当访问到str字符串最后的结束符‘\0’时结束回溯，返回true;
        if (str[pathLength] == '\0')
            return true;

        bool hasPath = false;
        //满足要求继续查找下一个字符:坐标在边界之内，str字符串中的字符出现在了初始矩阵里，改点未被访问过。
        if (row >= 0 && row < rows && col >= 0 && col < cols 
            && matrix[row * cols + col] == str[pathLength] 
            && !visited[row * cols + col])
        {
            //满足要求表示这点已经被访问了，路径长度加1，指向下一个字符，访问标志置为true;
            ++pathLength;
            visited[row * cols + col] = true;
            //调用自身从当前点开始检测四周是否有符合要求的点
            hasPath = hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength, visited)
                || 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+1, col, str, pathLength, visited);
            /*
            若有符合要求的字符串，则此次代码会在if (str[pathLength == '\0']) return true;中结束，并且返回true回到主程序
            若路径途中没有符合要求的字符串，则会回溯到上一步pathLength--中重新找下一个字符。
            */

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

        }
        return hasPath;
    }

};

更新代码及讲解

DFS具体讲解参考：https://blog.csdn.net/raphealguo/article/details/7560918

bool hasPath(const char* matrix, int rows, int cols, const char* str)
{
    if (matrix == nullptr || str == nullptr || rows <= 0 || cols <= 0)
        return false;
    //定义访问矩阵
    vector<vector<bool> >visit(rows, vector<bool>(cols, false));
    //记录遍历长度,遍历到str最后一位时，说明找到我们需要的字符串了
    int pathLength = 0;
    //按照数组从第一位开始遍历回溯
    for (int row=0; row < rows; ++row)
    {
        for (int col=0; col < cols; ++col)
        {
            //进入DFS判断(row,col)是否是解的一个点
            if (DFS(matrix, rows, cols, str, row, col, visit, pathLength))
                return true;
            //程序运行到这，表示从(row,col)出发找不到解，所以换一个节点开始
        }
    }
    return false;
}


bool DFS(const char* matrix, int rows, int cols, const char* str, int row, int col, vector<vector<bool> >& visit, int& pathLength)
{
    //回溯终止标志：若遍历到str结尾返回true;
    if (str[pathLength] == '\0')
        return true;
    //当(row,col)是其中一位字符且没有被访问过，则可以从这位开始遍历回溯
    if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == str[pathLength] && visit[row][col] == false)
    {
        //长度加1，访问位置true
        ++pathLength;
        visit[row][col] = true;
        /*
        这一位遍历完后，接着按照四个方向找下一位合适的字符，
        若由此点开始有满足要求的字符出现，则在这会返回true
        */
        if (DFS(matrix, rows, cols, str, row - 1, col, visit, pathLength) ||
            DFS(matrix, rows, cols, str, row, col + 1, visit, pathLength) ||
            DFS(matrix, rows, cols, str, row + 1, col, visit, pathLength) ||
            DFS(matrix, rows, cols, str, row, col - 1, visit, pathLength))
            return true;
        /*
        程序运行到这，表示这一位字符沿四个方向运行下去都没有找到合适的节点序列，所以必须从此点回溯。
        回溯之前将其重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中
        */
        --pathLength;
        visit[row][col] = false;
    }
    //到这里，针对(row,col)这一个点的遍历就结束了，返回true表示本次搜索没有找到解，主程序还得从下一个点入手找解
    return false;
}