剑指Offer：矩阵中的路径（Python语言实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指Offer：矩阵中的路径（Python语言实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1163字，纯文字阅读大概需要2分钟。

内容图文

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
如果一条路径经过了矩阵的某一格，那么该路径不能再进入该格子。

class Solution:
    def has_path(self, matrix, rows, cols, path):
        for ri in range(rows):
            for ci in range(cols):
                if matrix[ri*cols+ci] == path[0]:
                    if self.find(list(matrix), rows, cols, path[1:], ri, ci):
                        return True
        return False

    def find(self, matrix, rows, cols, path, ri, ci):
        if not path:
            return True
        matrix[ri*cols+ci] = '0'
        if ci < cols-1 and matrix[ri*cols+(ci+1)] == path[0]:
            return self.find(matrix, rows, cols, path[1:], ri, ci+1)
        elif ci > 0 and matrix[ri * cols + (ci - 1)] == path[0]:
            return self.find(matrix, rows, cols, path[1:], ri, ci-1)
        elif ri < rows - 1 and matrix[(ri + 1) * cols + ci] == path[0]:
            return self.find(matrix, rows, cols, path[1:], ri+1, ci)
        elif ri > 0 and matrix[(ri-1)*cols+ci] == path[0]:
            return self.find(matrix, rows, cols, path[1:], ri-1, ci)
        else:
            return False


st = Solution()
matrix = 'abtgcfcsjdeh'
path = 'bfce'
print(st.has_path(matrix, 3, 4, path))

通常在二维矩阵上找路径这类问题都可以应用回溯法解决。

（最近更新：2019年07月10日）

内容总结

以上是互联网集市为您收集整理的剑指Offer：矩阵中的路径（Python语言实现）全部内容，希望文章能够帮你解决剑指Offer：矩阵中的路径（Python语言实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端