面试题12：矩阵中的路径（c++）【剑指offer】

参考LeetCode讲解：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/hui-su-fa-shen-du-you-xian-sou-suo-by-bike666222/

class Solution {
public:
    int x[4]={0,0,-1,1};
    int y[4]={-1,1,0,0};
    bool hasPath(char* matrix, int rows, int cols, char* str){
        if(matrix==nullptr || str==nullptr || rows<1 || cols<1) return false;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                int idx=i*cols+j;
                if(matrix[idx]==str[0]){
                    if(dfs(matrix,rows,cols,str,i,j,idx,1)) return true;
                }
            }
        }
        return false;
    }

    bool dfs(char* matrix, int rows, int cols, char* str,int i, int j,int idx, int num){
        if(num==strlen(str)) return true;
        char tmp=matrix[idx];
        matrix[idx]='.';
        for(int k=0;k<4;k++){
            int d_x=x[k]+i;
            int d_y=y[k]+j;
            int newidx=d_x*cols+d_y;
            if(d_x>=0 && d_x<rows && d_y>=0 && d_y<cols && matrix[newidx]==str[num]){
                if(dfs(matrix,rows,cols,str,d_x,d_y,newidx,num+1)) return true;
            }
        }
        matrix[idx]=tmp;
        return false;
    }
};