如何在使用通过堆栈实现的迭代式DFS时回溯

Question

我正在完成这个Leetcode问题：https://leetcode.com/problems/word-search/和我随机选择了用while循环和堆栈迭代地实现DFS，但我在回溯时遇到了一些不便，如果我递归地完成了这个问题，通常就不会发生这种情况，例如，我只能考虑实现一个列表(visited_index)来跟踪我访问过的索引，并在回溯时将布尔矩阵visited设置回False。

from collections import defaultdict
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        starting_points = defaultdict(list)
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                starting_points[board[i][j]].append((i,j))
        
        
        start = starting_points[word[0]]
        visited = [[False] * n for _ in range(m)]
        stack = []
        directions = [(1,0), (0,-1), (-1,0), (0,1)]
        
        for s in start:
            stack.append((s[0], s[1], 0))
            visited_index = [] # EXTRA LIST USED
            while stack:
                x, y, count = stack.pop()
                while len(visited_index) > count:
                    i, j = visited_index.pop()
                    visited[i][j] = False # SETTING BACK TO FALSE WHEN BACKTRACKING
                if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or board[x][y] != word[count]:
                    continue
                else:
                    
                    visited[x][y] = True
                    visited_index.append((x,y))
                    if count + 1 == len(word):
                        return True
                    for d in directions:
                        i, j = x + d[0], y + d[1]
                        stack.append((i,j, count + 1))
            
            else:
                stack.clear()
                for i in range(m):
                    for j in range(n):
                        visited[i][j] = False
        return False

我相信在递归方法中，我可以在函数结束时将visited布尔值重新设置为False，而不需要使用额外的列表。在使用堆栈进行迭代DFS时，有没有人有什么建议不要引入额外的数据结构？

Answer 1

只要有子节点被处理，我就会将父节点保留在堆栈上。然后，当所有的子进程都已被处理，并且您从堆栈中弹出父进程时，您将有合适的时机删除该父进程的已访问标记。

实现该想法的一种方法是在放入堆栈的元组中再放入一条信息:所采用的最后一个方向。您可以使用该信息来查找下一个要采取的方向，如果有可用的有效方向，则使用该新方向将当前节点推回到堆栈上，然后在堆栈上推送相应的子节点。后者获得该“前一个”方向指示的一些默认值。例如-1。

我修改了你的代码以符合这个想法：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        stack = []
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    # 4th member of tuple is previous direction taken. -1 is none.
                    stack.append((i, j, 1, -1))  # count=1, side=-1
                
        visited = [[False] * n for _ in range(m)]
        directions = [(1,0), (0,-1), (-1,0), (0,1)]

        while stack:
            x, y, count, side = stack.pop()
            # perform the success-check here, so it also works for 1-letter words.
            if count == len(word):
                return True
            visited[x][y] = True  # will already be True when side > -1
            # find next valid direction
            found = False
            while side < 3 and not found:
                side += 1
                dx, dy = directions[side]
                i, j = x + dx, y + dy
                found = 0 <= i < m and 0 <= j < n and not visited[i][j] and board[i][j] == word[count]
            if not found:  # all directions processed => backtrack
                visited[x][y] = False
                continue
            stack.append((x, y, count, side))  # put node back on stack
            stack.append((i, j, count + 1, -1))
        return False