首页 > 试题广场 >

矩阵中的路径

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

输入

"ABCESFCSADEE",3,4,"ABCCED"

输出

true
示例2

输入

"ABCESFCSADEE",3,4,"ABCB"

输出

false
算法知识视频讲解
开通博客
头像 咪咪虾条001
发表于 2021-02-28 21:16:35
基本思想：0.根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次1.根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge 2.根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组 3.确定递 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 Captain66
发表于 2021-03-07 16:34:14
题目描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 典型的递归实现回溯的题目，必须熟练 public boo 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 翟邦杰
发表于 2021-03-03 21:09:58
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 江南好___
发表于 2021-03-29 17:06:33
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * @param matrix string字符串 * @param rows in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 让子弹憋飞
发表于 2021-04-16 17:02:54
题目描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如​ABCESFCSADEE矩阵中包含一条字符串"BCC 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 wowowo123
发表于 2021-03-24 17:34:11
注意这个题将二维矩阵以一维数组的形式存储 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param matrix string字符串 # @param rows int整型 # @param cols int整型 # @param str 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 morisa
发表于 2021-03-26 12:10:40
暴力回溯 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不经历怎么能成长
发表于 2021-03-29 10:52:26
变量含义：hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited)：返回值代表是否找到。matrix：地图矩阵 str判断的字符串。pathLength：str字符串的下标。rows cols 地图的行跟列用来模拟二维访问。row,co 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

回溯 dfs
上传者：牛客301499号
难度：
21条回答 5300浏览

热门推荐

通过挑战的用户

相关试题

矩阵中的路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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