矩阵中的路径

题目描述

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

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

第一思路

dfs，递归的办法

AC代码

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str){
        if (*str == '\0') {
            return true;
        }
        bool b = false;
        for (int i = 0; i < rows * cols; ++i){
            bool *flag = new bool[rows * cols]{false};
            b = b || havePath(matrix, matrix + i, rows, cols, str, flag);
            delete[] flag;
        }
        return b;
    }

    
    bool havePath(char* matrix,char* p, int rows, int cols, char* str, bool *flag){
        if (*str == '\0') {
            return true;
        }
        if (p < matrix || p > matrix + cols * rows || *(flag + (p - matrix)) || *str != *p) {
            return false;
        }
        else {
            *(flag + (p - matrix)) = true;
            return havePath(matrix, p - 1, rows, cols, str + 1, flag)
            || havePath(matrix, p + 1, rows, cols, str + 1, flag)
            || havePath(matrix, p - cols, rows, cols, str + 1, flag)
            || havePath(matrix, p + cols, rows, cols, str + 1, flag);
        }
    }
};

需要注意的点是每一次for循环里都重新生成false数组