矩阵中的路径C++回溯算法

回溯算法的基本思想，先选中矩阵中任意一位置作为起点，与字符串首字母进行匹配，若匹配则选择当前位置前后左右四个邻居节点继续与字符串的下一字母进行匹配，以此类推，若不匹配则回溯到前一状态。如此反复，字符串匹配完毕为止。具体思路见代码注释。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(str==nullptr || strlen(str)==0){
            return true;
        }
        if(rows<=0 || cols<=0){
            return false;
        }
        // 选择不同的起点
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(hasPath(matrix, rows, cols, str, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
    // 回溯核心
    // 这里rows/cols表示矩阵总的行列数（从1开始数），row/col表示当前回溯到的行列数（从0开始）
    // 故row的最大有效值为rows-1，col同。 
    // index表示当前比较的字符为str[index]， 故index<=strlen(str)-1
    bool hasPath(char* matrix, int rows, int cols, char* str, 
                    int index, int row,  int col)
    {
        //边界条件
        if(strlen(str)==index){
            return true;
        }
        if(row>=rows || col>=cols || row<0 || col<0){
            return false;
        }

        // 如果矩阵中可以正确找到str[index]
        if(str[index]==matrix[row*cols+col]){
            // 记录当前矩阵元素
            int tmp = matrix[row*cols+col]; 
            // 将该元素设置为0， 表示已访问
            matrix[row*cols+col] = 0; 
            // 继续向下寻找，任一路径满足条件即可
            if ( hasPath(matrix, rows, cols, str, index+1, row, col+1) ||
                 hasPath(matrix, rows, cols, str, index+1, row, col-1) ||
                 hasPath(matrix, rows, cols, str, index+1, row+1, col) ||
                 hasPath(matrix, rows, cols, str, index+1, row-1, col) ){
                return true;
            }
            // 都不满足，复位之前的状态
            matrix[row*cols+col] = tmp;
        }
        return false;
    }


};