回溯法——矩阵中的路径

回溯法
回溯法可以看成蛮力法的升级版，它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。

用回溯法解决的问题的所有选项可以形象地用树状结构来表示。

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

class Solution:
    def find_str(self, target, matrix, rows, columns):
        if target is None or matrix is None or rows <= 0 or columns <= 0:
            raise Exception('Nothing')
        current_char = 0
        for r in range(rows):
            for c in range(columns):
                if self.has_path(target, matrix, rows, columns, r, c, current_char):
                    return True
        return False
    
    def has_path(self, _str, matrix, rows, cols, r, c, current_char, used_label=None):
        if current_char == len(_str):
            return True
        if not used_label:
            used_label = {(row, col): 0 for row in range(rows) for col in range(cols)}
        ret = False
        
        if r >=0 and c >=0 and r < rows and c < cols and not used_label[(r, c)] and matrix[r][c] == _str[current_char]:
            current_char += 1
            used_label[(r, c)] = 1
            ret = self.has_path(_str, matrix, rows, cols, r+1, c, current_char, used_label) or  \
                      self.has_path(_str, matrix, rows, cols, r-1, c, current_char, used_label) or \
                      self.has_path(_str, matrix, rows, cols, r, c+1, current_char, used_label) or \
                      self.has_path(_str, matrix, rows, cols, r, c-1, current_char, used_label)
            if not ret:
                current_char -= 1
                used_label[(r, c)] = 0
        return ret
        '''
        if matrix[r][c] != _str[current_char]:
            return False
        
        if used_label[(r, c)] == 1:
            return False
        
        current_char += 1
        if current_char == len(_str):
            return True
        used_label[(r, c)] = 1
        
        action = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for r_change, c_change in action:
            r = r + r_change
            c = c + c_change
            if r < 0 or c < 0 or r == rows or c == cols:
                continue
            if not self.has_path(_str, matrix, rows, cols, r, c, current_char, used_label):
                continue
        return True
        '''