题解 | #矩阵中的路径#

// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  * 
//  * @param matrix char字符型二维数组 
//  * @param word string字符串 
//  * @return bool布尔型
//  */
// function hasPath( matrix ,  word ) {
//     // write code here
//     let n = matrix.length
//     let m = matrix[0].length
//     let end=word.length
//     let words=word.split('')
//     //let used = new Array(n).fill(0).map(()=>new Array(m).fill(0))
//     //这里也不用这么再声明一个used数组来标记是否可以走
//     for(let i = 0;i<n;i++){
//         for(let j = 0;j<m;j++){
// //             let start=0
// //             if(matrix[n][m]==word[start]){
// //                 if(matrix[n+1][m])
// //                 if(matrix[n][m+1])
// //                 if(matrix[n-1][m])
// //                 if(matrix[n][m-1])
//             //写不出dfs算法
//             if(dfs(matrix,words,i,j,0)){
//             return true
//               }             
//             }
//         }
//     return false
      
// }

//  function dfs(matrix,word,p,q,index){
//      if(p<0||p>matrix.length-1||q<0||q>matrix[0].length-1||matrix[p][q]!==word[index]){
//          return false
//      }
//      if(index===word.length-1){
//          return true
//      }
//      let tmp=matrix[p][q]
//      matrix[p][q]='0'//used
//      let res=dfs(tmp,word,p+1,q,index+1)|| dfs(tmp,word,p,q+1,index+1)|| 
//          dfs(tmp,word,p-1,q,index+1)|| dfs(tmp,word,p,q-1,index+1)  
//      matrix[p][q]=tmp 
//      return res   
     
//  }
// module.exports = {
//     hasPath : hasPath
// };

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */
function hasPath( matrix ,  word ) {
    // write code here
    //遍历
    let words = word.split('')
    for(let i=0;i<matrix.length;i++){
        for(let j=0;j<matrix[0].length;j++){
            if(dfs(matrix,words,i,j,0)){return true} //分析matrix[i][j]元素作为开头字符是否有匹配路径
        }
    }
    return false
}
function dfs(matrix,word,i,j,index){
    if(i>matrix.length-1||i<0||j>matrix[0].length-1||j<0||matrix[i][j]!==word[index]){return false} //此条路径排除
    if(index===word.length-1) {return true} //匹配上了并且index已经与word长度对应，说明全部匹配，返回真
    let temp=matrix[i][j]
    matrix[i][j]='0' //改为一个不可能匹配的值，防止走走过的路径
    //分别对应               下                              上                               右                               左
    let 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) 
    if(res){
        return true
    }else{
         matrix[i][j]=temp //回溯
        return false
    }
    
    ### matrix[i][j]=temp //回溯
    ### return res
    其他题解的这里是这样写的。我实在没有看懂回溯体现在哪里 我还是觉得按照上面的方式才体现出     回溯，这种写法感觉就是无论怎么都回溯了很怪，但是为什么他还是可以通过
    
  
}
module.exports = {
    hasPath : hasPath
};