每日一练（剑指offer）矩阵中的路径

描述

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

示例

输入：

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"

返回值：

true

思路

对于一个矩阵，首先应该遍历所有的节点，尝试把每一个节点当作入口点，代入到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布尔型
*/
static int row=0;//记录矩阵
static int col=0;//记录矩阵列数
static int len=0;//记录字符串长度
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;
    }
bool 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;

}

链接

​​https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6​​