首页 > 试题广场 >

矩阵中的路径

[编程题]矩阵中的路径
  • 热度指数：87917 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
数据范围：,
示例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

备注:
0 <= matrix.length <= 200
0 <= matrix[i].length <= 200
算法知识视频讲解
开通博客
头像 幸福的火龙果在干饭
发表于 2021-07-13 20:57:07
精华题解 一、题目描述 JZ65矩阵中的路径题目大意：请判断一个矩阵是否存在一条包含某字符串所有字符的路径。路径可以从矩阵的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个个子，则该路径不能再进入该格子。注意审题：不能重复走相同的位置 二、算法（回溯） 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Zhuwanxing
发表于 2021-07-18 22:33:51
精华题解 题目链接 https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 数据结构和算法
发表于 2021-07-03 22:40:42
回溯算法解决 回溯算法实际上一个类似枚举的搜索尝试过程，也就是一个个去试，我们解这道题也是通过一个个去试，下面就用示例1来画个图看一下 我们看到他是从矩形中的一个点开始往他的上下左右四个方向查找，这个点可以是矩形中的任何一个点，所以代码的大致轮廓我们应该能写出来，就是遍历矩形所有的点，然后从这个点 展开全文
去ta的博客 赞 (84) 回复(7) 收起
头像 牛客题解官
发表于 2022-04-25 18:57:51
题中的主要信息： 矩阵中上下左右随便移动，找到给定字符串的路径 访问可以重复，但是作为路径不能往回走 举一反三： 学习完本题的思路你可以解决如下题目： JZ13. 机器人的运动范围 方法：递归（推荐使用） 知识点：递归与回溯 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它 展开全文
去ta的博客 赞 (17) 回复(3) 收起
头像 卷过卷心菜
发表于 2021-04-06 13:30:19
首先不确定第一个字母的初始位置，遍历寻找一遍，找到初始位置，设置访问数组，通过一系列条件判断 import java.util.*; public class Solution { public boolean hasPath (char[][] matrix, String word) 展开全文
去ta的博客 赞 (15) 回复(3) 收起
头像 1666
发表于 2021-04-01 23:56:30
public boolean hasPath (char[][] matrix, String word) { int rows = matrix.length; if (rows == 0) return false; int cols = matrix[0].length 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 不经历怎么能成长
发表于 2021-04-02 15:18:17
出口：当word 下标走到数组大小，代表找到word当x,y 超出边界，或该数被访问，或matrix位置字符不与word的位置上的相同 都结束返回false。if(index == word.size()) return true;if(x < 0 || x >= matrix.size 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 tonyjxc
发表于 2022-01-24 14:09:55
第五十题 回溯第一题 一开始看代码挺长的，起始很简单，注意回溯返回之前状态的时候所有东西都要回到之前的状态。所以递归调用的时候没有用引用 class Solution { public:     /**      * 代码中的类名、方法 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 蓉城小晋
发表于 2021-11-22 15:21:49
```/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型二维数组 * @param word string字符串 * @return bool布尔型 */ function hasPath( 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 夜渡寒鸦呀
发表于 2022-06-10 21:31:35
C语言 矩阵中的路径 解题思路 一道典型的DFS深度优先算法的回溯问题。对于一个矩阵，首先应该遍历所有的节点，尝试把每一个节点当作入口点，代入到DFS算法，计算DFS(matrix,word,i,j,0); DFS深度优先算法 dfs(matrix,word,i,j,index) 正确口条件：ind 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 已注销
发表于 2022-01-22 23:04:59
回溯法需要考虑很多条件，如下： 1、超过边界，需要返回到原来的索引位置 2、没超过边界，但是没有找到值，需要返回到原来的索引位置 3、没超过边界，找到值 3.1 找到值之和，需要把找到的值设置为*，防止word中存在重复的元素，当循环查找时候，若存在重复元素，而没有将之前走过的路径设置为*，就会存在 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 已注销
发表于 2022-03-25 15:53:38
回溯算法步骤： 主函数： 遍历矩阵 在每一个点调用dfs() 如果dfs返回true就返回true dfs： 边界判断，判断输入的坐标是否在矩阵范围内，判断字符串是否被遍历完，是就返回true 存下当前坐标值 更改当前坐标对应值 4个方向上递归调用dfs 恢复当前坐标到原值 返回递归调用结果 代 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

dfs
上传者：牛客301499号
难度：
110条回答 4304浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩阵中的路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号