首页 > 试题广场 >

矩阵中的路径

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

输入

"ABCESFCSADEE",3,4,"ABCCED"

输出

true
示例2

输入

"ABCESFCSADEE",3,4,"ABCB"

输出

false
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-02 11:04:06
精华题解 描述 这是一篇针对初学者的题解，给出一个比较好的DFS模板。知识点:DFS难度：二星 题解 题目描述：给定一个二维字符串矩阵mat,和一个字符串str,判断str是否可以在mat中匹配。可以选择的方向是上下左右。 方法：DFS 这道题大家都知道是DFS的题，关键是怎么可以快速并且正确的写出，是本题 展开全文
去ta的博客 赞 (36) 回复(5) 收起
头像 初憶
发表于 2019-08-18 18:33:33
矩阵中的路径 题目描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d 展开全文
去ta的博客 赞 (33) 回复(2) 收起
头像 用月光取暖
发表于 2019-08-12 11:26:54
题解 public int[][] visit; public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { visit = new int[rows][cols]; char[] 展开全文
去ta的博客 赞 (22) 回复(2) 收起
头像 一叶浮尘
发表于 2020-03-20 23:39:32
很久不做这种深度优先遍历和广度优先遍历的题目，有点眼生。后面几道题目应该都是和深度优先遍历和广度优先遍历有关的题目，这种题目就不能再依靠高级数据结构的思想来帮助我们解决问题，要纯靠自己的思维能力来进行解决了。 这道题目自己的思维局限是没有理解广度优先遍历要掌握的诀窍导致写代码的时候出现了死循环，而且 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 牛客437913218号
发表于 2020-02-27 22:29:51
这道题坑太多了，思路虽然简单，但是想考虑得完整太难了。 class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { if (matrix == nullptr 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Oh~Sunny
发表于 2020-02-11 16:31:03
此题采用回溯发来进行求解,在说之前我想告诉大家,如果大家看过之前别人提交的py版本的代码,会发现不能通过全部的测试用例,现在我根据剑指offer书中的思路写下如下py的代码,希望您批评指正!!! class Solution: def hasPath(self, matrix, rows, 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Dan2
发表于 2019-09-14 12:33:21
答题中很多都是采用递归方式实现，思路直接，简单。但是如果采用非递归实现方式实现，该怎么实现呢？下面就解释一下如何通过非递归方式实现。路径寻找过程中，整体的节点构成了一个树形结构，树形结构通过根节点互相连接。 1.定义一个marks数组标记当前的节点是否访问过，被访问过的节点，我们把他们叫做关键节点， 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 轨轨=
发表于 2020-02-17 19:07:23
【回溯法】 与力扣79题同理 class Solution { public: int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int n,m; int len; bool f[10100]; bool dfs(char* 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 王清楚
发表于 2020-09-22 16:47:06
比较裸的搜索题，从矩阵的每一个位置开始搜索，看能不能达成一个成功的字符串这道题给出的矩阵是按一维字符串给的。所以(x,y)应该是x*cols+y #include<iostream> #include<cstring> using namespace std; class S 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 橙子爱吃桃子
发表于 2020-04-25 01:25:16
C++/代码： class Solution { public: int col,row; //定义全局变量 bool hasPath(char* matrix, int rows, int cols, char* str){ //char* matrix 二维数组用一维数组表示 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 海上的烟火9527
发表于 2020-03-04 15:18:31
大多数都是递归？我本人喜欢迭代，其实递归肯定可以转迭代的，借助入栈退栈实现，事实上这也是计算机递归底层的原理。数据结构C语言版清华教材栈那一章有个走迷宫，和这个一样原理。对任意一个格子查找上下左右是否有符合的字符，没有就标记已经走过（借助辅助数组）然后退栈，换个方向继续搜索，思路很简单。只要注意边界 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

回溯 dfs
难度：
672条回答 109643浏览

热门推荐

通过挑战的用户

相关试题

矩阵中的路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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