深度优先遍历

核心伪代码

boolean[] visited;
boolean DFS(Node n, int d){
    visited = new boolean[n.size()]
    if(isEnd(n, d)){    //达到一个满足状态 可能是遍历了所有节点 可能是找到了了一条路径
        return true;
    }
    for(Node nextNode in n){
        if(visted[nextNode]) return false;  //当前节点已经搜索过了
        visited[nextNode] = true;
        if(DFS(nextNode, d+1)) return true;
        visited[nextNode] = false;  //如果当前节点的子节点搜索失败 则将当前节点设置为为访问继续开始其他子节点                      
    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 __init__(self):
        self._dict = {}
        self.count = 0
    
    def get_sum(self, i, j):
        num = 0
        while i:
            temp = i % 10
            i = i /10
            num += temp
        while j:
            temp = j %10
            j = j /10
            num += temp
        return num
    
    def dfs(self, matrix, k, i, j):
        if not (0 <= i < len(matrix) and 0 <= j < len(matrix[0])):
            return
        if self.get_sum(i, j) > k:
            return
        if self._dict.get((i,j)) is not None:
            return
        self._dict[(i,j)] = 1
        self.count += 1
        self.dfs(matrix, k, i+1, j)
        self.dfs(matrix, k, i-1, j)
        self.dfs(matrix, k, i, j+1)
        self.dfs(matrix, k, i, j-1)
    
    def movingCount(self, threshold, rows, cols):
        x = [[1 for i in range(cols)] for j in range(rows)]
        self.dfs(x, threshold, 0, 0)
        return self.count

例题二

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

class Solution:
    def __init__(self):
        self._dict = {}
    
    def hasPath(self, matrix, rows, cols, path):
        x = [list(matrix[i*cols:(i+1)*cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                self._dict = {}
                if(self.dfs(x, i ,j, path)):
                    return True
        return False
    
    def dfs(self, matrix, i, j, path):
        if not (0 <= i <len(matrix) and 0 <= j < len(matrix[0])):
            return False
        if matrix[i][j] != path[0]: #如果不等于path的当前字母 则不符合
            return False
        if self._dict.get((i,j)) is not None:
            return False
        self._dict[(i,j)] = 1
        if not path[1:]:
            return True
        return self.dfs(matrix, i+1, j, path[1:]) 
        return self.dfs(matrix, i-1, j, path[1:]) 
        return self.dfs(matrix, i, j+1, path[1:]) 
        return self.dfs(matrix, i, j-1, path[1:])