矩阵中的路径

function hasPath( matrix ,  word ) {
    let m = matrix.length,n = matrix[0].length;
    function dfs(i,j,k=0){ // 第k个字符
        if(i<0 || i>=m || j<0 || j>=n||word[k]!==matrix[i][j] || matrix[i][j]===0) return false;
        if(k === word.length-1) return true;
        let temp = matrix[i][j];
        matrix[i][j] = 0;
        if(dfs(i,j+1,k+1) || dfs(i,j-1,k+1) || dfs(i-1,j,k+1) || dfs(i+1,j,k+1)){
            return true;
        } 
        matrix[i][j] = temp;
        return false;
    }
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(dfs(i,j,0)){
                return true;
            }
        }
    }
    return false;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */
function hasPath( matrix , word ) {
    // write code here
    let rows = matrix.length;
    let cols = matrix[0].length;
    let flag = new Array((rows-1)*(cols-1)).fill(null);
    for(let i=0;i<rows;i++){
        for(let j=0;j<cols;j++){
            //循环遍历二维数组，找到七点啊等于word第一个元素的值，再递归判断四周是否有符合条件的第二个值
            if(judge(matrix,i,j,rows,cols,flag,word,0)){
                return true;
            }
        }
    }
    return false;
}
function judge(matrix,i,j,rows,cols,flag,word,k){
    //根据i和j计算匹配的第一个元素转为一维数组的未知
    let index=i*cols+j;
    //递归终止条件
    if(i<0||j<0||i>=rows||j>=cols||matrix[i][j]!=word[k]||flag[index]==true){
        return false;
    }
    //k的初始值为0，若k已经到达word末尾了，说明都已经匹配成功了，直接返回true
    if(k==word.length-1){
        return true
    }
    //要走的第一个位置为true，表示已经走过了
    flag[index]=true;
    //回溯，递归寻找 每次找到给k加1，找不到就还原
    if(judge(matrix,i-1,j,rows,cols,flag,word,k+1)||
       judge(matrix,i+1,j,rows,cols,flag,word,k+1)||
       judge(matrix,i,j-1,rows,cols,flag,word,k+1)||
       judge(matrix,i,j+1,rows,cols,flag,word,k+1)){
        return true
    }
    //走到这，说明这一条路不通，还原尝试其他路径
    flag[index]=false;
    return false;
}
module.exports = {
    hasPath : hasPath
};