题解 | #矩阵中的路径#

class Solution {
  public:
    /*参数说明  k 字符串索引初始为0即先判断字符串的第一位*/
    bool judge(char* matrix, int rows, int cols, int i, int j, char* str, int k,
               bool* flag) {
        //因为是一维数组存放二维的值，index值就是相当于二维数组的（i，j）在一维数组的下标
        int index = i * cols + j;
        //flag[index]==true,说明被访问过了，那么也返回true;
        if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] ||
                flag[index] == true)
            return false;
        //字符串已经查找结束，说明找到该路径了
        if (str[k + 1] == '\0') return true;
        //向四个方向进行递归查找,向左，向右，向上，向下查找
        flag[index] =
            true;//标记访问过 //要走的第一个位置置为true，表示已经走过了0

        //回溯，递归寻找，每次找到了就给k加一，找不到，还原
        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] = false;
        return false;
    }

    bool hasPath(char* matrix, int rows, int cols, char* str) {
        if (matrix == NULL || rows < 1 || cols < 1 || str == NULL) return false;
        bool* flag = new bool[rows * cols];
        memset(flag, false, rows * cols);
        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;
                }
            }
        }
        delete[] flag;
        return false;
    }
};