题解 | #矩阵中的路径#

基本递归，注意用#标记matrix中已经走过的路径，递归完后复原路径。

class Solution {
public:
    char* matrix, *str;
    int rows, cols, len;
    bool hasPath2(int i, int j, int index) {
        if (index == len - 1) return true;
        bool res = false;
        char tmp = matrix[i * cols + j];
        matrix[i * cols + j] = '#';
        if (i > 0 && matrix[(i - 1) * cols + j] == str[index + 1]) res = res || hasPath2(i - 1, j, index + 1);
        if (i < rows - 1 && matrix[(i + 1) * cols + j] == str[index + 1]) res = res || hasPath2(i + 1, j, index + 1);
        if (j > 0 && matrix[i * cols + j - 1] == str[index + 1]) res = res || hasPath2(i, j - 1, index + 1);
        if (j < cols - 1 && matrix[i * cols + j + 1] == str[index + 1]) res = res || hasPath2(i, j + 1, index + 1);
        matrix[i * cols + j] = tmp;
        return res;
    }

    bool hasPath(char* matrix, int rows, int cols, char* str) {
        len = 0;
        while (str[len] != '\0') len++;
        if (len == 0 || rows == 0 || cols == 0) return false;
        this->matrix = matrix;
        this->str = str;
        this->rows = rows;
        this->cols = cols;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i * cols + j] == str[0]) {
                    if (hasPath2(i, j, 0)) return true;
                }
            }
        }
        return false;
    }


};