首页 > 试题广场 >

矩阵中的路径

[编程题]矩阵中的路径

热度指数：85609 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n,m \le 20\$ , $1\le len \le 25\$

示例1

输入

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

输出

true

示例2

输入

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

输出

false

算法知识视频讲解

JavaScript

IPzzzi

function hasPath( matrix ,  word ) {
    // write code here
    for(var i=0;i<matrix.length;i++){
      for(var j=0;j<matrix[0].length;j++){
          if(dfs(matrix,word,i,j,0)) return true;
      }
    }
    return false;
}

var dfs = function(matrix,word,i,j,k){
    if(i<0 || j<0 || i>=matrix.length||j>=matrix[0].length|| matrix[i][j]!=word[k]) return false;
    if(k==word.length-1) return true;
    var tmp = matrix[i][j];
    matrix[i][j] = '/';   //实际上每次回溯都会产生一个变量tmp，不会覆盖前面的值，变成'/'是为了不走重复路
    var res = dfs(matrix,word,i+1,j,k+1) || dfs(matrix,word,i-1,j,k+1)||
                dfs(matrix,word,i,j+1,k+1) || dfs(matrix,word,i,j-1,k+1);  
    matrix[i][j] = tmp;  //四周找不到的时候，将该值重置回原来的值
    return res;   //然后回溯上一个值，继续遍历它的四周，如果还是不符合，继续重置回溯的那个值
}
//参考CSDN大佬，原文链接：https://blog.csdn.net/my_z_1234/article/details/108056048

发表于 2021-04-19 10:57:13 回复(0)

JavaScript

球球来一个offer吧

js代码，思想通用

判断matrix中有没有这条路径，那就从word中第一个字符开始寻找，后面的字符递归就行了。

判断第一个字符有没有存在，满足三点就行：

①当前节点出界了

②这个格子已经走过了

③这个格子中的字符不是我们要找的

如果以上三点任意一点满足的话，就return false，否则这个格子就是我们要找的。

当该格子是要找的格子后，判断后面的格子，使用递归判断上下左右即可。

只需要注意一点，如果某一个方向的格子不对，那就回溯，重新来过，判断其他方向。

一些细节部分的注释直接写在代码中了。

function hasPath( matrix ,  word ) {
    // write code here
    if(!matrix){  //矩阵为空时
        return false;
    }
    let m = matrix.length;  //矩阵行数
    let n = matrix[0].length;  //矩阵列数
    let used = new Array(m);  //创建二维数组used，用来存放走过的路径
    for(let i = 0; i < m; i++){
        used[i] = new Array(n);
    }
    
    let canFind = function(row, col, ind){  //创建canFind函数，用来判断该节点是否正确
        if(ind == word.length){   //递归结束条件。当索引超过word长度时还没有返回false的话，就返回true
            return true;
        }
        if(row < 0 || row >= m || col < 0 || col >= n){  //当该节点超过边界时返回false
            return false;
        }
        if(used[row][col] || matrix[row][col] !== word[ind]){  //当该节点已经走过时，或者该节点
            return false;                                      //不是我们想要找的字符时，返回false
        }
        used[row][col] = true;    //以上false条件判断完后，就说明该节点是正确的字符，将其used设为true
        let canFindRest = canFind(row + 1, col, ind + 1) || canFind(row, col + 1, ind + 1) || canFind(row - 1, col, ind + 1) || canFind(row, col - 1, ind + 1);
        if(canFindRest){  //利用递归canFindRest寻找该节点的上下左右四个点，如果找到了，就返回true
            return true;
        }else{  //如果没找到，就利用回溯，将该节点的used设为false，重新寻找后面的三个条件
            used[row][col] = false;
            return false;
        }    
    }
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(canFind(i, j, 0)){   //遍历matrix，寻找第一个节点，如果函数返回true，说明有这条路径
                return true;
            }
        }
    }
    return false;   //遍历完也没找到，就返回false
}

发表于 2021-04-07 09:33:25 回复(1)