矩阵中的路径

int flag = 0;
int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
bool dfs(char** matrix,int x,int y,char* word,int row,int col)
{
    if(*word == '\0')
        flag = 1;
    for(int i=0;i<4;i++)
    {
        int tx = x+next[i][0];
        int ty = y+next[i][1];
        if(tx<0 || tx>=row || ty <0 || ty >=col)
            continue;
        if(matrix[tx][ty] != '.' && matrix[tx][ty] == *word)
        {
            char c = matrix[tx][ty];
            matrix[tx][ty] = '.';
            dfs(matrix,tx,ty,word+1,row,col);
            matrix[tx][ty] = c;
        }
    }
    if(flag == 1)
        return true;
    return false;
}
bool hasPath(char** matrix, int matrixRowLen, int* matrixColLen, char* word ) 
{
    // write code here
    int len = strlen(word);
    for(int i =0;i<matrixRowLen;i++)
    {
         for(int j =0;j<*matrixColLen;j++)
         {
            if(matrix[i][j] == word[0])
            {
                char c = matrix[i][j];
                matrix[i][j] = '.';
                if(dfs(matrix,i,j,word+1,matrixRowLen,*matrixColLen))
                    return true;
                matrix[i][j] = c;
            }
         }
    }
    return false;
}

int hasPath(char** matrix, int matrixRowLen, int* matrixColLen, char* word ) {
    //创建一个辅助数组，并初始化 
    int have[matrixRowLen][*matrixColLen];
    //用一个visit数组记录行为    先上后下再左最后向右
    int visit[25];
    for(int i=0;i<matrixRowLen;i++){
        for(int j=0;j<(*matrixColLen);j++){
            //当第一个字符匹配时
            int p=0;   //这个是用于访问字符串的计数器
            if(matrix[i][j]==word[p]){   //如果该元素与字符串第一个元素相同则开始找元素
                //将记录数组清零和动作的数组清零
                memset(visit,0,sizeof(visit));
                memset(have,0,sizeof(have));
                //下标，i1和j1即为当前位置
                int i1=i,j1=j;
                //将此处做标记，第一个数字自动标记
                have[i1][j1]=1;
                //循环结束的标志是p计数器小于0或者已经访问到了字符串末尾
                while(p>=0&&word[p]!='\0'){
                    //看当前visit[p]动作数组的值  
                    switch(visit[p]){
                        case 0:if(i1-1>=0&&have[i1-1][j1]==0&&word[p+1]==matrix[i1-1][j1]) {
                            have[i1--][j1]=1;//向上走了
                            visit[p]=1;     //最后一次访问p执行的是向上转操作
                            p++; break;
                        }
                        case 1:if(i1+1<matrixRowLen&&have[i1+1][j1]==0&&word[p+1]==matrix[i1+1][j1]) {
                            have[i1++][j1]=1;//向下转了
                            visit[p]=2;     //最后一次访问p执行的是向下转转操作
                            p++; break;
                        }
                            //向上判断边界是否为0
                        case 2:if(j1-1>=0&&have[i1][j1-1]==0&&word[p+1]==matrix[i1][j1-1]) {
                            have[i1][j1--]=1;//向左
                            visit[p]=3;     //最后一次访问p执行的是向左走操作
                            p++; break;
                        }
                        case 3:if(j1+1<(* matrixColLen)&&have[i1][j1+1]==0&&word[p+1]==matrix[i1][j1+1]) {
                            have[i1][j1++]=1;//向右
                            visit[p]=4;     //最后一次访问p执行的是向右走操作
                            p++; break;
                        }
                        //如果不匹配那么 看是否已经访问完了字符串
                        default:{
                            //如果访问完了字符串，那么直接return
                            if(word[p+1]=='\0') return 1;  //如果访问到了数组末尾则返回正确
                            else{
                                //否则就要进行回溯
                                //那么此时的元素被标记为未访问
                                have[i1][j1]=0;
                                //如果此时的元素是第一个元素
                                if(p<=0){
                                    p--;
                                    break;
                                }
                                else{
                                    //检查上一次数组的动作，根据上一次的动作来修改下标
                                    switch(visit[--p]){
                                        case 1: i1++;break;
                                        case 2: i1--;break;
                                        case 3: j1++;break;
                                        case 4: j1--;break;
                                    }
                                }
                                
                            }
                        }
                    
                }
            }
        }
    }
    }
    return 0;
}