剑指offer——矩阵中的路径C++

dfs+回溯。此处回溯的思想大概就是自动回溯？
1.char*和string可以直接比较。
2.bool数组必须手动fill，不然不是全为false的。
3.传输组，形参要写数组，实参写数组名，因为相当于传一个指针，所以回改变实参的值。

class Solution {
public:
    //此字符串不是二级指针，不会改变原来的值，所以不用erase尾部
    //传的是一个数组，其实相当于传进去一个指向数组首部地址的指针，会改变原数组的值
    bool dfs(char* matrix, int rows, int cols,int i, int j, char* str, int k, bool vis[]){
        int index = i * cols + j;
        if(i<0 || i>=rows || j<0 || j>=cols || matrix[index] != str[k] || vis[index] == true)
            return false;
        //已经检查到最后一位了，而且上面的检查是相等的
        if(strlen(str)-1 == k) return true;
        vis[index] = true;
        if(dfs(matrix,rows,cols,i-1,j,str,k+1,vis) || dfs(matrix,rows,cols,i+1,j,str,k+1,vis)||
          dfs(matrix,rows,cols,i,j-1,str,k+1,vis) || dfs(matrix,rows,cols,i,j+1,str,k+1,vis))
            return true;
        vis[index] = false;//如果这条路走不通，记得将这个点设为未访问，这样别的路还可以再次访问这个点
        return false;
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        //vis数组+dfs(回溯应该就是递归内部自动会回的),走到无路可走应该要之前的分岔路口看看
        //根据现在字符在矩阵中的位置判断能往哪里走，返回多个方向的dfs值，只要有一个正确即可
        //给的是一个c_style字符串，不能用矩阵来处理，要通过当前行列来判断现在是哪个字符
        if(strlen(str) > strlen(matrix) || matrix == "\0" || str == "\0") return false;
        bool vis[strlen(matrix)];
        fill(vis,vis+strlen(matrix),false);
        //上面rows是总的行列，此处的row是当前的行列
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(dfs(matrix,rows,cols,i,j,str,0,vis)) return true;
            }
        }
        return false;
    }
};