题目描述

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

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

解题思路

这个题可以通过回溯算法进行求解。回溯算法也称为试探法，即进行下一步测试，若不成功，则返回上一步继续寻找其他方法，知道成功。

首先遍历矩阵，找到与字符串首个元素相同的字符；
然后在遍历找到的这个字符的前col + 1后col - 1,上row - 1下row + 1，
通过回溯法找到与字符串的下一个字符相同的字符作为新起点，继续遍历新字符的上下左右，寻找新的字符，直到找到所有字符，返回true;否则返回false;

为了防止重复查找同一个字符，需要设置一个同样大小的标志矩阵，用于标记是否被遍历过。

代码

class Solution
{
public:
    bool hasPath (char* matrix, int rows, int cols, char* str)
    {
        if (matrix == NULL || rows < 1 || cols < 1 || str == NULL)
            return false;
        int lenpath = 0; // 字符串中字符的下标
        bool* visit = new bool[rows * cols]; // 创建一个和矩阵一样大小的标志矩阵
        memset(visit, 0, rows * cols); // 创建一个全为 0 的标志矩阵 visit
        // 遍历矩阵，找到与字符串第一个字符相等的字符
        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                if (hasPathCore(matrix, rows, cols, row, col, lenpath, visit, str))
                {
                    delete[] visit;
                    return true;
                }
            }
        }
        delete[] visit;
        return false;
    }
private:
    // 回溯算法
    bool hasPathCore (char* matrix, int rows, int cols, int row, int col, int& lenpath, bool* visit, char* str)
    {
        if (str[lenpath] == '\0') // 递归结束的条件
            return true;
        
        bool haspath = false; // 当前尝试路径是否成功
        if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == str[lenpath] && !visit[row * cols + col])
        {
            lenpath++;// 寻找字符串的下一个字符
            visit[row * cols + col] = true; // 说明当前字符已经遍历过了
            
            // 寻找矩阵中下一个相同的字符
            haspath = hasPathCore(matrix, rows, cols, row - 1, col, lenpath, visit, str) || 
                hasPathCore(matrix, rows, cols, row + 1, col, lenpath, visit, str) || 
                hasPathCore(matrix, rows, cols, row, col - 1, lenpath, visit, str) || 
                hasPathCore(matrix, rows, cols, row, col + 1, lenpath, visit, str) ;
            if (!haspath) // 若当前路径不成功，返回上一步，继续寻找
            {
                lenpath--;
                visit[row * cols + col] = false;
            }
        }
        return haspath;
    }
};

void *memset(void *s, int ch, size_t n);

函数功能：将s所指向的某一块内存中的前n个字节的内容全部设置为ch指定的ASCII值，第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为指向s的指针，它是对较大的结构体或数组进行清零操作的一种最快方法。

参考博文链接：https://cuijiahua.com/blog/2018/02/basis_65.html

zerofly's Blog

矩阵中的路径

题目描述

解题思路

代码