Пройдя рекурсивный 2-мерный двоичный массив и посчитав количество единиц, через которые нужно пройти

Question

Я пытаюсь изучать программирование, и одна концепция, которую я действительно пытаюсь понять, это рекурсия.

Изменить: Ниже приведена ссылка на изображение фактического вопроса, который объясняет инструкции намного лучше. Я думаю, что мое объяснение было не самым лучшим.

Инструкция

Я пытаюсь написать программу, использующую рекурсию на python, которая принимает двумерный двоичный массив A [0, ..., n-1] [0, ..., n-1] и возвращает минимум количество «1», которое необходимо пройти, чтобы достичь конечной точки. Начальная точка A [0] [0], а конечная точка A [n-1] [n-1]. Вы можете перемещать только одну ячейку за раз, перемещая одну ячейку вправо или одну ячейку вниз. Массив содержит только 0 и 1. Это похоже на лабиринт, где нужно пройти через 0, а 1 - как стена, но здесь можно и, вероятно, нужно будет пройти через несколько 1. Выходными данными будет минимальное число единиц, необходимое для прохождения, чтобы достичь конечной точки.

Я не уверен, что это правильный подход. Я думаю, что мне может быть лучше с 1 функцией. Я также не могу понять, как подсчитать количество опасных зон, которые необходимо пройти. Я думаю, вы можете заметить, что я новичок в этом, и я был бы признателен, если бы кто-то мог привести меня в правильном направлении.

def minCellsTravel(grid):

    gridWidth = len(grid[0])
    gridHeight = len(grid)

    def helperFn(row, col):

            # if we already reached the rightmost end
            if row == gridHeight-1 and col == gridWidth-1:
                    return grid[row][col]

            start = grid[row][col]
            downMove = None
            if row < gridHeight - 1:
                    downMove = start + helperFn(row + 1, col)

            rightMove = None
            if col < gridWidth - 1:
                    rightMove = start + helperFn(row, col + 1)

            if rightMove and downMove:
                    return min(rightMove, downMove)
            elif rightMove:
                    return rightMove
            else:
                    return downMove

Answer 1

Нечто подобное должно сработать

def solve(row, col, A):

    if (row == A.shape[0] - 1) and (col == A.shape[1] - 1):
        return A[row][col]
    if (row >= A.shape[0]) or (col >= A.shape[1]):
        return A.shape[0] + A.shape[1]

    left = solve(row + 1, col, A)
    right = solve(row, col + 1, A)
    best_path = min(right, left)

    return best_path + A[row][col]

Идея состоит в том, что в каждой ячейке вы можете идти направо или вниз, и лучшее решение, начинающееся с этой ячейки, - это лучшее решение, начинающееся с ячейки справа от вас, или лучшее решение, начинающееся с ячейки слева от вас. Возьмите лучший плюс значение текущей ячейки, и вы получите решение, начинающееся с текущей ячейки.

Хотя эту проблему можно решить с помощью рекурсии, динамическое программирование является более эффективным, если вы решите этот вопрос, если вам интересно.