核心偽代碼

boolean[] visited;
boolean DFS(Node n, int d){
    visited = new boolean[n.size()]
    if(isEnd(n, d)){    //達到一個滿足狀態(tài) 可能是遍歷了所有節(jié)點 可能是找到了了一條路徑
        return true;
    }
    for(Node nextNode in n){
        if(visted[nextNode]) return false;  //當前節(jié)點已經搜索過了
        visited[nextNode] = true;
        if(DFS(nextNode, d+1)) return true;
        visited[nextNode] = false;  //如果當前節(jié)點的子節(jié)點搜索失敗 則將當前節(jié)點設置為為訪問繼續(xù)開始其他子節(jié)點                      
    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:])