剑指offer-python-回溯法-矩阵中的路径
2024-10-07 08:26:46
这个系列主要详细记录代码详解的过程。
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
思路:构建一个辅助矩阵,将所有的内容置为True,该辅助矩阵的大小与原矩阵大小一致。然后使用递归遍历原矩阵,同时给辅助矩阵标号,每递归一次将辅助矩阵的值置为False, 若不存在,则将辅助矩阵的值置为True。
class Solution:
def hasPath(self, matrix, rows, cols, path):
assistMatrix = [True]*rows*cols
for i in range(rows):
for j in range(cols):
if(self.hasPathAtAStartPoint(matrix,rows,cols, i, j, path, assistMatrix)):
return True
return False def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, assistMatrix):
if not path:
return True
index = i*cols+j
if i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=path[0] or assistMatrix[index]==False:
return False
assistMatrix[index] = False
if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],assistMatrix) or
self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],assistMatrix) or
self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],assistMatrix) or
self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],assistMatrix)):
return True
assistMatrix[index] = True
return False
最新文章
- SQLServer------存储过程在C#中的使用方法
- 教程Xcode 4下编译发布与提交App到AppStore
- jQuery hover demo
- Servlet课程0425(五) sendRedirect实现不同页面共享数据
- [Client]动检参数讨论与ONVIF
- xml中不能直接添加ViewGroup
- Android(Lollipop/5.0) Material Design(六) 使用图像
- Apache2.4 137行 httpd-ahssl.conf
- Javascript面向对象编程(二):构造函数的继承
- Activity工作过程
- NLP+词法系列(一)︱中文分词技术小结、几大分词引擎的介绍与比较
- lightoj 1025 区间dp
- loadrunner&#160;脚本优化-参数化之Parameter&#160;List参数取值
- js里面的判断最好做到完全控制
- Android8.0运行时权限策略变化和适配方案
- ASP.NET AJAX入门系列(2):使用ScriptManager控件
- lwip lwiperf 方法进行性能测试 4.5MB/S
- Unix/Linux系统中僵尸进程是如何产生的?有什么危害?如何避免?
- Microsoft .NET Framework 安装未成功(证书方面)
- springmvc导出excel(POI)