剑指offer 矩阵中的路径回溯

我不是女神ヾ 2022-05-21 23:40 161阅读 0赞

# coding:utf-8
    
    # !/usr/bin/env python
    
    # Time: 2018/6/11 9:09
    
    # Author: sty
    
    # File: Findpath.py
    
    next_state = [[0, -1], [0, 1], [1, 0], [-1, 0]]
    
    class MatrixPath():
        def has_path(self, array, rows, cols, str):
            if rows == 0 or cols == 0:
                return False
            matrix = []
            marked = [[False] * cols for _ in range(rows)]
            row_info = []
            index = 0
            for row in range(rows):
                for col in range(cols):
                    row_info.append(array[index])
                    index += 1
                matrix.append(row_info)
                row_info = []
            for row in range(rows):
                for col in range(cols):
                    if self.judge(matrix, str, marked, 0, row, col, rows, cols):
                        return True
            return False
    
        def judge(self, matrix, str, marked, path_len, row, col, rows, cols):
            if path_len == len(str):
                return True
            if row < 0 or row >= rows or col < 0 or col >= cols or matrix[row][col] != str[path_len] \
                    or marked[row][col] is True:
                return False
            marked[row][col] = True
            for n in next_state:
                # 这里的path_len+1很容易忘记，同时row和col也要相应的变化
                if self.judge(matrix, str, marked, path_len + 1, row+n[0], col+n[1], rows, cols):
                    return True
            marked[row][col] = False
            return False
    
    
    
    a = MatrixPath()
    print(a.has_path('abcesfcsadee', 3, 4, 'bcced'))
    print(a.has_path('abcesfcsadee', 3, 4, 'abcb'))