矩阵中的路径

这道题坑太多了，思路虽然简单，但是想考虑得完整太难了。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if (matrix == nullptr || str == nullptr || rows < 1 || cols < 1)
            return false;
        bool* markmatrix = new bool[rows * cols]();
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                memset(markmatrix, 0, rows * cols);
                if (hasPathCore(matrix, rows, cols, str, i, j, markmatrix))
                    return true;
            }
        }
        return false;
    }
    bool hasPathCore(char* matrix, int rows, int cols, char* str, int x, int y, bool* markmatrix)
    {
        if (*str == 0)
            return true;
        if (*str == matrix[x * cols + y])
        {
            if (*(str + 1) == 0)
                return true;
            markmatrix[x * cols + y] = true;
            cout << x << "   " << y << endl;
            bool a = false, b = false, c = false, d = false;
            if (x + 1 < rows && markmatrix[(x + 1) * cols + y] == false)
                a = hasPathCore(matrix, rows, cols, str+1, x + 1, y, markmatrix);
            if (x - 1 >= 0 && markmatrix[(x - 1) * cols + y] == false)
                b = hasPathCore(matrix, rows, cols, str+1, x - 1, y, markmatrix);
            if (y + 1 < cols && markmatrix[x * cols + y + 1] == false)
                c = hasPathCore(matrix, rows, cols, str+1, x, y + 1, markmatrix);
            if (y - 1 >= 0 && markmatrix[x * cols + y - 1] == false)
                d = hasPathCore(matrix, rows, cols, str+1, x, y - 1, markmatrix);
            markmatrix[x * cols + y] = false;
            return a || b || c || d;
        }
        else
        {
            return false;
        }
    }
};

遇到的坑

• x、y与rows、cols的关系傻傻分不清。
• 代码复制非常容易出问题
• 不应该最后用循环到最后*str==0来判断是否有序列，因为如果序列个数和矩阵元个数相等，就没有多余的位置循环换都\0.
• 写法还可以再优化，把所有条件判断都放到前面判断，四个递归调用只管传参数，不用管是否有效。