回溯法

矩阵中的路径

题目

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

矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路

回溯法

代码

class Solution:
    """ 在矩阵中寻找是否存在路径等于给定的字符串
    
    Returns:
        matrix -- 寻找路径的字符矩阵
        rows   -- 矩阵的行数
        cols   -- 矩阵的列数
        path   -- 待寻找的路径

    """
    def hasPath(self, matrix, rows, cols, path):
        # 为了保证当前路径上已经被访问过的结点不再重复访问
        # 设置 vis 来标记某个元素是否被访问过，容量和 matrix 相同
        vis = [True] * rows * cols

        for i in range(rows):
            for j in range(cols):
                # 从 matrix[i][j] 开始寻找是否存在路径
                if self.hasPathAtAStartPoint(matrix, rows, cols, i, j, path, vis):
                    # 如果存在则返回True
                    return True
        # 如果从所有位置出发都不能找到，则返回False
        return False

    # 从某个点(x, y)出发寻找路径
    def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, vis):
        # 1. index 表示当前访问元素的位置
        index = i * cols + j

        # 2. 递归的终止条件
        # 如果路径被搜索到了最终位置，存在则返回True
        if not path:
            return True
        
        # 3. 如果访问越出边界、当前位置元素不是path的起始元素或者当前位置已被访问过，直接返回False
        if i < 0 or i >= rows or j < 0 or j >= cols or \
                    matrix[index]!=path[0] or vis[index]==False:
            return False
        
        # 如果没有找到则将当前位置重新置为False
        # 关键步骤， 先标记为False， 不让子寻找会使用该点
        vis[index] = False

        # 递归条件,如果以(0, 0)作为原点
        # 向上走: i - 1
        # 向下走: i + 1
        # 向前走: j + 1
        # 向后走: j _ 1
        if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],vis)):
            return True
        # 关键步骤
        # 如果没找到，不需要占用该点，需要释放
        vis[index] = True
        
        return False

机器人的运动范围

题目

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路

回溯法

代码

class Solution:
    def movingCount(self, threshold, rows, cols):
        # 用来标记坐标是否走过的二维矩阵
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        count = self.findgrid(threshold, rows, cols, matrix, 0, 0)
        return count

    def findgrid(self, threshold, rows, cols, matrix, i, j):
        count = 0
        # matrix[i][j]==0表示没走过这一格
        if i<rows and j<cols and i>=0 and j>=0 and \
                    self.judge(threshold, i, j) and matrix[i][j] == 0: 
            matrix[i][j] = 1  # 表示已经走过了
            count = 1 + self.findgrid(threshold, rows, cols, matrix, i, j+1) \
            + self.findgrid(threshold, rows, cols, matrix, i, j-1) \
            + self.findgrid(threshold, rows, cols, matrix, i+1, j) \
            + self.findgrid(threshold, rows, cols, matrix, i-1, j)
        return count
    
    def judge(self, threshold, i, j):
        if sum(map(int, str(i) + str(j))) <= threshold:
            return True
        else:
            return False