首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
矩阵中的路径
[编程题]矩阵中的路径
热度指数:436941
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 64M,其他语言128M
算法知识视频讲解
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如
矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
示例1
输入
"ABCESFCSADEE",3,4,"ABCCED"
输出
true
示例2
输入
"ABCESFCSADEE",3,4,"ABCB"
输出
false
马上挑战
算法知识视频讲解
提交运行
算法知识视频讲解
添加笔记
求解答(0)
邀请回答
收藏(1455)
分享
提交结果有问题?
672个回答
55篇题解
开通博客
牛客题解官
发表于 2020-06-02 11:04:06
精华题解
描述 这是一篇针对初学者的题解,给出一个比较好的DFS模板。知识点:DFS难度:二星 题解 题目描述:给定一个二维字符串矩阵mat,和一个字符串str,判断str是否可以在mat中匹配。可以选择的方向是上下左右。 方法:DFS 这道题大家都知道是DFS的题,关键是怎么可以快速并且正确的写出,是本题
展开全文
初憶
发表于 2019-08-18 18:33:33
矩阵中的路径 题目描述:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d
展开全文
用月光取暖
发表于 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[]
展开全文
一叶浮尘
发表于 2020-03-20 23:39:32
很久不做这种深度优先遍历和广度优先遍历的题目,有点眼生。后面几道题目应该都是和深度优先遍历和广度优先遍历有关的题目,这种题目就不能再依靠高级数据结构的思想来帮助我们解决问题,要纯靠自己的思维能力来进行解决了。 这道题目自己的思维局限是没有理解广度优先遍历要掌握的诀窍导致写代码的时候出现了死循环,而且
展开全文
牛客437913218号
发表于 2020-02-27 22:29:51
这道题坑太多了,思路虽然简单,但是想考虑得完整太难了。 class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { if (matrix == nullptr
展开全文
Oh~Sunny
发表于 2020-02-11 16:31:03
此题采用回溯发来进行求解,在说之前我想告诉大家,如果大家看过之前别人提交的py版本的代码,会发现不能通过全部的测试用例,现在我根据剑指offer书中的思路写下如下py的代码,希望您批评指正!!! class Solution: def hasPath(self, matrix, rows,
展开全文
Dan2
发表于 2019-09-14 12:33:21
答题中很多都是采用递归方式实现,思路直接,简单。但是如果采用非递归实现方式实现,该怎么实现呢?下面就解释一下如何通过非递归方式实现。路径寻找过程中,整体的节点构成了一个树形结构,树形结构通过根节点互相连接。 1.定义一个marks数组标记当前的节点是否访问过,被访问过的节点,我们把他们叫做关键节点,
展开全文
轨轨=
发表于 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*
展开全文
王清楚
发表于 2020-09-22 16:47:06
比较裸的搜索题,从矩阵的每一个位置开始搜索,看能不能达成一个成功的字符串这道题给出的矩阵是按一维字符串给的。所以(x,y)应该是x*cols+y #include<iostream> #include<cstring> using namespace std; class S
展开全文
橙子爱吃桃子
发表于 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 二维数组用一维数组表示
展开全文
海上的烟火9527
发表于 2020-03-04 15:18:31
大多数都是递归?我本人喜欢迭代,其实递归肯定可以转迭代的,借助入栈退栈实现,事实上这也是计算机递归底层的原理。数据结构C语言版清华教材栈那一章有个走迷宫,和这个一样原理。对任意一个格子查找上下左右是否有符合的字符,没有就标记已经走过(借助辅助数组)然后退栈,换个方向继续搜索,思路很简单。只要注意边界
展开全文
问题信息
回溯
dfs
难度:
672条回答
1455收藏
108304浏览
热门推荐
通过挑战的用户
打不死的黄妖精
2023-03-07 09:36:39
牛客61374...
2023-02-27 02:46:12
repus
2022-09-13 21:57:01
牛客95625...
2022-09-10 15:23:48
牛客96505...
2022-09-08 12:00:40
相关试题
利用回溯法求下列不等式的所有整数解...
dfs
评论
(10)
来自
乐视2017秋招开发工程...
数字字符串转化成IP地址
字符串
回溯
评论
(198)
农夫、羊、菜和狼的故事
搜索
回溯
思维
评论
(48)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
有20000人的就餐需求,现建了一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
import java.util.*; public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { } }
class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { } };
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): # write code here
class Solution { public bool hasPath(string matrix, int rows, int cols, string path) { // write code here } }
function hasPath(matrix, rows, cols, path) { // write code here } module.exports = { hasPath : hasPath };
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ func hasPath( matrix string , rows int , cols int , path string ) bool { // write code here }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # @param matrix string字符串 # @param rows int整型 # @param cols int整型 # @param path string字符串 # @return bool布尔型 # class Solution def hasPath(matrix, rows, cols, path) # write code here end end
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ def hasPath(matrix: String,rows: Int,cols: Int,path: String): Boolean = { // write code here } }
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ fun hasPath(matrix: String,rows: Int,cols: Int,path: String): Boolean { // write code here } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ public boolean hasPath (String matrix, int rows, int cols, String path) { // write code here } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ export function hasPath(matrix: string, rows: number, cols: number, path: string): boolean { // write code here }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ func hasPath ( _ matrix: String, _ rows: Int, _ cols: Int, _ path: String) -> Bool { // write code here } }
struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ pub fn hasPath(&self, matrix: String, rows: i32, cols: i32, path: String) -> bool { // write code here } }
"ABCESFCSADEE",3,4,"ABCCED"
true
"ABCESFCSADEE",3,4,"ABCB"
false