BFS vs DFS

from collections import deque                       
                                                      
def get_neighbors(r, c):       
  for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
    yield r + dr, c + dc

def exist(board, word):
    rows, cols = len(board), len(board[0])
    word_len = len(word)

    for r in range(rows):
        for c in range(cols):
            if board[r][c] != word[0]:
                continue

            queue = deque()
            queue.append((r, c, 0, {(r, c)}))  # (row, col, index in word, visited set)

            while queue:
                row, col, idx, visited = queue.popleft()

                if idx == word_len - 1:
                    return True

                for nr, nc in get_neighbors(row, col):
                    if (0 <= nr < rows and 0 <= nc < cols and 
                        (nr, nc) not in visited and 
                        board[nr][nc] == word[idx + 1]):
                        
                        new_visited = visited.copy()
                        new_visited.add((nr, nc))
                        queue.append((nr, nc, idx + 1, new_visited))

    return False

  new_visited = [row_v[:] for row_v in visited]
  new_visited[row][col] = True
  
  for nr, nc in get_neighbors(row, col):
      stack.append((nr, nc, idx + 1, new_visited))

def exist(board, word):
    rows, cols = len(board), len(board[0])
    word_len = len(word)

    for r in range(rows):
        for c in range(cols):
            if board[r][c] != word[0]:
                continue

            stack = [(r, c, 0, set())]

            while stack:
                row, col, idx, visited = stack.pop()

                if (row < 0 or row >= rows or col < 0 or col >= cols or 
                    (row, col) in visited or board[row][col] != word[idx]):
                    continue

                if idx == word_len - 1:
                    return True

                new_visited = visited.copy()
                new_visited.add((row, col))

                for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                    nr, nc = row + dr, col + dc
                    stack.append((nr, nc, idx + 1, new_visited))

    return False

  new_visited = [row_v[:] for row_v in visited]
  new_visited[row][col] = True
  
  for nr, nc in get_neighbors(row, col):
      stack.append((nr, nc, idx + 1, new_visited))