【剑指offer】矩阵中的路径

这道题卡住的原因是new数组的初始化方法没有弄清楚
C++的动态数组里，string这样的类类型是会自动调动默认构造函数初始化，但是基本数据类型是不会自动初始化的，需要在后面加上括号初始化成默认值，如本题bool数组初始化为false，否则内存是脏的，不能AC
M,N 分别为矩阵行列大小， K 为字符串 word 长度。
时间复杂度 O(3^KMN)
最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K)；矩阵***有 MN 个起点，时间复杂度为 O(MN) 。
方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 O(3^K)
**空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MN ，递归深度为 MN ，此时系统栈使用 O(MN) 的额外空间。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str) {
        bool* flag = new bool[strlen(matrix)]();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (judge(matrix, rows, cols, i, j, str, 0, flag))
                    return true;
            }
        }
        return false;
    }

    bool judge(char* matrix, int rows, int cols, int i, int j, char* str, int k, bool* flag) {
        int index = i * cols + j;
        if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1)
            return false;
        if(k == strlen(str) - 1) return true;
        flag[index] = 1;
        if (judge(matrix, rows, cols, i - 1, j, str, k + 1, flag)
                || judge(matrix, rows, cols, i + 1, j, str, k + 1, flag)
                || judge(matrix, rows, cols, i, j - 1, str, k + 1, flag)
                || judge(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {
            return true;
        }
        flag[index] = 0;
        return false;
    }
};