12. 矩阵中的路径 回溯法（backtracking）

backtrac.py

#!/usr/bin/env python3
# https://cyc2018.github.io/CS-Notes/#/notes/12.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84
# https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc?f=discussion

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if not matrix:
            return False
        if not path:
            return True
        x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if self.exist_helper(x, i, j, path):
                    return True
        return False

    def exist_helper(self, matrix, i, j, p):
        if matrix[i][j] == p[0]:
            if not p[1:]:
                return True
            matrix[i][j] = ''   # NOTE:
            if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
                return True
            if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
                return True
            if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
                return True
            if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
                return True
            matrix[i][j] = p[0]  # NOTE:
            return False
        else:
            return False

def main():
    # path = ['b', 'c', 'c', 'c', 'e', 'd']
    path = ['b', 'c', 'c', 'e', 'd']

    matrix = ['a', 'b', 'c', 'e',
              's', 'f', 'c', 's',
              'a', 'd', 'e', 'e']
    rows = 3
    cols = 4

    result = Solution()
    if result.hasPath(matrix, rows, cols, path):
        print(str(path) + " has path!")
    else:
        print(str(path) + " no path!")

if __name__ == '__main__':
    main()