矩阵中的路径 牛客网 剑指Offer
2024-08-31 02:07:16
矩阵中的路径 牛客网 剑指Offer
- 题目描述
- 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
class Solution:
def hasPathCore(self, matrix, rows, cols, row,col,path,pathLength,visited):
if len(path) == pathLength:
return True
hasPath = False
if row >= 0 and row < rows and col >=0 and col < cols \
and matrix[row * cols + col] == path[pathLength] \
and not visited[row * cols +col]:
pathLength +=1
visited[row * cols + col] = True
hasPath = self.hasPathCore(matrix,rows,cols,row,col-1,path,pathLength,visited) or \
self.hasPathCore(matrix,rows,cols,row - 1,col,path,pathLength,visited) or \
self.hasPathCore(matrix,rows,cols,row,col + 1,path,pathLength,visited) or \
self.hasPathCore(matrix,rows,cols,row+1,col,path,pathLength,visited)
if not hasPath:
pathLength -= 1
visited[row*cols + col] = False
return hasPath
def hasPath(self, matrix, rows, cols, path):
if matrix == None or rows < 1 or cols < 1 or path == None:
return False
visited = [0] * (rows * cols)
pathLength = 0
for row in range(rows):
for col in range(cols):
if self.hasPathCore(matrix,rows,cols,row,col,path,pathLength,visited):
return True
return False
最新文章
- Uva 11248 网络扩容
- iTool拷贝app到电脑上
- php 方便快捷导出excel
- js——倒计时
- Ubuntu12.04安装中文字体(转)
- 2015年4月 15款免费jQuery插件
- 第二好用的时间日期选择插件(jscal)
- 基于express框架的应用程序骨架生成器介绍
- treecnt
- 【Spark2.0源码学习】-3.Endpoint模型介绍
- 破解Oracle ERP 密码
- 小程序入口构造工具&;二维码测试工具
- 完全数java
- ASP.NET MVC之从控制器传递数据到视图方式
- 2018/03/07 每日一个Linux命令 之 cat
- ssh REMOTE HOST IDENTIFICATION HAS CHANGED!
- mysql 从库执行insert失败导致同步停止
- Jmeter(二十三)_插件扩展
- 报错:Validation failed for one or more entities. See 'EntityValidationErrors' property for more details.
- iterm2用法与技巧
热门文章
- 聊一聊开闭原则(OCP).
- 谈谈raft fig8 —— 迷惑的提交条件和选举条件
- Tars | 第0篇 腾讯犀牛鸟开源人才培养计划Tars实战笔记目录
- 解决sofaboot项目右键入口方法没有run sofa application
- 【PHP数据结构】栈的相关逻辑操作
- 前端常用场景总结CSS/JS/插件(实用篇更新中...)
- Docker系列(2)- Docker中的名词概念
- python学习笔记(十五)-异常处理
- 接口测试-Mock测试方法
- flask项目在Linux运行