题解 | #矩阵中的路径#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */
// 深度优先算法dfs
function hasPath( matrix , word ) {
    let arr = [...word];
    // 遍历整个矩阵，将其中某元素作为起始点调用dfs函数进行搜索
    for(let i = 0; i < matrix.length; i++){
        for(let j = 0; j < matrix[0].length; j++){
            if(dfs(matrix, arr, i, j, 0)){
                return true;
            }
        }
    }
    return false;
}
function dfs(matrix, arr, i, j, index){
    // 如果越界或当前字符不匹配目标字符，则返回false
    if(i > matrix.length - 1 || i < 0 || j > matrix[0].length - 1 || j < 0 || matrix[i][j] !== arr[index]){
        return false;
    }
    // 如果已经匹配到了目标单词的最后一个字符，则返回true
    if( index === arr.length - 1){
        return true;
    }
    let temp = matrix[i][j];
    // 将当前字符标记为已访问
    matrix[i][j] = '0';
    // 按照上下左右四个方向查找，其中任意一个匹配则赋值为true
    let res = dfs(matrix, arr, i + 1, j, index + 1) 
    || dfs(matrix, arr, i - 1, j, index + 1) 
    || dfs(matrix, arr, i, j + 1, index + 1) 
    || dfs(matrix, arr, i, j - 1, index + 1);
    // 回溯到上个字符，回复当前字符的原始值
    matrix[i][j] = temp;
    return res;
}
module.exports = {
    hasPath : hasPath
};