C语言 矩阵中的路径

解题思路

一道典型的DFS深度优先算法的回溯问题。对于一个矩阵，首先应该遍历所有的节点，尝试把每一个节点当作入口点，代入到DFS算法，计算DFS(matrix,word,i,j,0);

DFS深度优先算法

dfs(matrix,word,i,j,index)

正确口条件：index=strlen(word)，错误出口条件: i,j超出矩阵边界，或者当前word[index]!=matrix[i][j];如果满足条件，则将matrix[i][j]置为v，表示已经visit过该节点，之后不能再经过该节点，然后继续调用dfs(matrix,word,[上下左右四个点],index+1)，之后将visit的点还原为原值即可。

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @param word string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int row=0;//记录矩阵行数
static int col=0;//记录矩阵列数
static int len=0;//记录字符串长度
/*
* @brief 深度优先搜索算法 
* @param matrix 矩阵
* @param word 字符串
* @param i ,j 矩阵起始坐标
* @param index 字符串起始位置
*/
int dfs(char **matrix,char *word,int i,int j,int index){
    int len=strlen(word);
    if(index==len)
        return 1;
    //边界条件判断 超出矩阵范围 或者单词和矩阵字符不一致
    if(i>=row||i<0||j>=col||j<0||matrix[i][j]!=word[index])
        return 0;
    //这一步 标记矩阵 说明已经visit
    char temp=matrix[i][j];
    matrix[i][j]='.';
    //上下左右遍历下一个字符
    int res=dfs(matrix,word,i+1,j,index+1)||dfs(matrix,word,i-1,j,index+1)||
        dfs(matrix,word,i,j+1,index+1)||dfs(matrix,word,i,j-1,index+1);
    matrix[i][j]=temp;
    return res;
        
}

int hasPath(char** matrix, int matrixRowLen, int* matrixColLen, char* word ) {
    // write code here
    //先进行特殊情况判断 字符串为空
    if(word==NULL)
        return 1;
    //矩阵为空
    if(matrixRowLen==0||*matrixColLen==0)
        return 0;
    len=strlen(word);
    col=* matrixColLen;
    row=matrixRowLen;
    //先寻找入口点
    for(int i=0;i<row;i++){
        //遍历矩阵列
        for(int j=0;j<col;j++){
           if(dfs(matrix,word,i,j,0))
               return 1;
            
        }
    }
    return 0;
}