возвращать конфликты в рекурсивной функции

Question

Я пишу функцию для решения задачи поиска слов . Однако я столкнулся с затруднительным положением, как правильно получить возвращаемое значение из моей рекурсивной функции dfs. Вот в чем проблема: если я использую ключевое слово return в последней строке кода, оно преждевременно заканчивается for direction in [[0,1],[0,-1],[1,0],[-1,0]] l oop, как только произойдет возврат. Однако, если я удалю return в последней строке, рекурсивная функция будет работать со штрафами, но никогда не вернет True из оператора if len(word)==0:print("TRUE") return True, даже если оператор выполняется. Я в основном понимаю, что как только программа наберет return, она проигнорирует все коды после нее. Не могли бы вы объяснить, как выбраться из этой ловушки?

def dfs(cur, board, word):
    board[cur[0]][cur[1]] = None
    print(cur, board, word)
    if len(word)==0:
        print("TRUE")
        return True   

    for direction in [[0,1],[0,-1],[1,0],[-1,0]]:
        Doard = copy.deepcopy(board)
        x = cur[0]+ direction[0]
        y = cur[1]+ direction[1]
        if x>len(board)-1 or x<0 or y>len(board[0])-1 or y<0:
            continue
        if Doard[x][y] == word[0]:
            Doard[x][y] = None
            return dfs([x,y], Doard, word[1:])  # Problematic RETURN keyword here

Answer 1

Совет, который дает вам @kszl, хорош, проверьте результат рекурсивного вызова и верните, только если он True, иначе позвольте l oop воспроизвести и вернуть False в конце вашей функции .

Вы остановили свою функцию, которая запускает поиск dfs() только в тех точках на доске, где находится первая буква word - я воссоздал это. Проблемы, которые я вижу с вашим кодом: вы deepcopy() слишком рано заходите на доску, многие из ваших копий никогда не используются; ваше использование x и y сбивает с толку, если не инвертировать, я переключился на row и column ниже; вы заменяете буквы на None в двух местах в dfs(), но должны делать это только в одном.

Моя переработка вашего кода:

from copy import deepcopy

board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
]

def dfs(current, board, word):
    if not word:
        return True

    current_row, current_column = current
    rows, columns = len(board), len(board[0])
    first, rest = word[0], word[1:]

    for r, c in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        row = current_row + r
        column = current_column + c

        if not (0 <= row < rows and 0 <= column < columns):
            continue

        if board[row][column] == first:
            clone = deepcopy(board)
            clone[row][column] = None

            if dfs((row, column), clone, rest):
                return True

    return False

def search_starting_letter(board, word):
    rows, columns = len(board), len(board[0])

    for row in range(rows):
        for column in range(columns):
            if board[row][column] == word[0]:
                clone = deepcopy(board)
                clone[row][column] = None

                if dfs((row, column), clone, word[1:]):
                    return True

    return False

word = "ABCCED"

print(search_starting_letter(board, word))