Построение цикла опорного плана транспортной задачи

Решить задачу на Python.

Дана матрица опорного плана транспортной задачи (частный случай задач оптимизации) в виде двумерного массива (количество столбцов для каждой строки постоянно и неизменно):

matrix = [
    [50, 0, 0, 0, 0],
    [0, 60, 0, 0, 40],
    [50, 10, 50, 40, 0]
]

Требуется написать функцию find_cycle, принимающую в качестве аргументов:

• позицию (строка, столбец) нулевой клетки, с которой надо построить цикл
• матрицу, в которой нужно построить цикл;

Функция должна возвращать список кортежей, обозначающих вершины (строка, столбец), через которые проходит цикл. Порядок вершин цикла в списке друг за другом так, как они находятся в цикле.

Запрещено использовать любые библиотеки, в т.ч. встроенные (NumPy, SciPy, Pandas и т.д.)

Правила нахождения цикла в матрице:

1. Цикл всегда строится от нулевой клетки;
2. Для любой матрицы цикл всегда существует, при этом он единственен для конкретной нулевой клетки (других циклов для данной нулевой клетки построить нельзя);
3. Цикл начинается и заканчивается в одной и той же нулевой клетке;
4. Цикл поворачивает только в заполненных базисных клетках матрицы опорного плана (те клетки, где есть числа);
5. Цикл всегда поворачивает под углом 90 градусов (вершина1 в строке → вершина1 в столбце → вершина2 в строке → и т.д.);
6. Цикл может "перепрыгивать" любое количество базисных клеток, если это необходимо;
7. Цикл может иметь различную форму (прямоугольник, квадрат, несколько прямоугольников и т.д.)

Примеры работы функции (для матрицы из примера выше):

>>> find_cycle((0, 1), matrix)
[(2, 1), (2, 0), (0, 0), (0, 1)]

>>> find_cycle((0, 2), matrix)
[(2, 2), (2, 0), (0, 0), (0, 2)]

>>> find_cycle((0, 3), matrix)
[(2, 3), (2, 0), (0, 0), (0, 3)]

>>> find_cycle((0, 4), matrix)
[(1, 4), (1, 1), (2, 1), (2, 0), (0, 0), (0, 4)]

>>> find_cycle((1, 0), matrix)
[(1, 1), (2, 1), (2, 0), (1, 0)]

>>> find_cycle((1, 2), matrix)
[(2, 2), (2, 1), (1, 1), (1, 2)]

>>> find_cycle((1, 3), matrix)
[(2, 3), (2, 1), (1, 1), (1, 3)]

>>> find_cycle((2, 4), matrix)
[(2, 1), (1, 1), (1, 4), (2, 4)]

UPD: мое решение выглядит так, полагаю, что я неправильно сделал условия добавления вершин в общий список (строки с pathloop.append(neighbor_row) и pathloop.append(neighbor_col)).

В моем тексте рассуждения:

• Фиктивный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке НЕТ другого соседа
• Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед

UPD2: у меня есть две идеи по решению это задачи, но я вообще не понимаю, как их можно реализовать:

1. Через цикл (но тогда надо правильно написать условие добавления вершин в цикл): фактически мы составляем цикл только по нормальным соседям (Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед)., поэтапно проверяя их на нормальность сначала по строке, затем по столбцу. Всех нормальных добавляем в список, всех фиктивных - пропускаем.

2. Через рекурсию - так как в строке/столбце у нас может быть несколько соседей, то каждого надо проверить на нормальность, что отчасти похоже на рекурсивный алгоритм:

   1. поэтапно (один за другим) проверяем всех соседей в данной строке/столбце на нормальность;
   2. если хотя бы один оказался фиктивным, то все соседи, проверенные до него являются фиктивными и их как вершины нашего цикла мы не добавляем в список вершин. Это может работать так: Для point == (0, 2) вершины (1, 1), (2, 1) и (1, 4) являются фиктивными, так как у них нет нормальных соседей, и мы их не должны добавить в список вершин.
   3. рано или поздно мы найдем нормального соседа, которого и добавим в список вершин

def neighbors(pos: tuple, matrix: list) -> list:
    """
    Вернуть координаты ненулевых фиктивных и нормальных соседей указанной ячейки по строке и столбцу

    Ненулевой сосед - такая ячейка матрицы, которая не равна нулю и самой себе.
    Соседи могут находится по строке и столбцам соответственно

    Фиктивный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке НЕТ другого соседа
    Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед
    """
    # создаем структуру для хранения соседей
    neighbors = {"row": [], "col": []}
    # записываем позицию, вокруг которой будем искать соседей
    crow, ccol = pos
    
    # ищем соседей по колонке
    for row in range(len(matrix)):
        # если найденное значение ненулевое и его позиция не равна заданной
        if matrix[row][ccol] != 0 and pos != (row, ccol):
            # это наш сосед по столбцу
            neighbors["col"].append((row, ccol))

    # ищем соседей по строке
    for col in range(len(matrix[0])):
        # если найденное значение ненулевое и его позиция не равна заданной
        if matrix[crow][col] != 0 and pos != (crow, col):
            # это наш сосед по строке
            neighbors["row"].append((crow, col))

    # возвращаем словарь соседей
    return neighbors


def find_cycle(matrix: list, point: tuple):
    """
    m: чистая матрица
    point: координаты ПУСТОЙ точки, с которой должен начинаться цикл

    :return: list
    """
    # копируем матрицу, чтобы не изменять глобальный объект
    m_copy = matrix
    # записываем строку столбец переданной позиции
    row, column = point
    # по переданной позиции в копии матрицы начальную клетку делаем -1
    m_copy[row][column] = -1
    
    # список вершин
    pathloop = []

    # сохраняем координаты точки
    local_point = point

    # пока искомая точка не находится в списке вершин
    while point not in pathloop:
        
        # ищем ненулевых соседей по строке
        neighbors_by_row =  neighbors(local_point, m_copy)["row"]

        # для каждого из них...
        for i, neighbor_row in enumerate(neighbors_by_row):
            # ...найдем соответствующего соседа по столбцу
            neighbors_by_col = neighbors(neighbor_row, m_copy)["col"]
            
            # если мы нашли такого ненулевого соседа по столбцу
            if neighbors_by_col:
                # то для первого попавшегося из них...
                # как я понимаю - ошибка где то тут, в условии сохранения соседей как вершин
                for j, neighbor_col in enumerate(neighbors_by_col):
                    # сохраним найденного соседа по строке как вершину цикла
                    pathloop.append(neighbor_row)

                    # сохраним найденного соседа по столбцу как вершину цикла
                    pathloop.append(neighbor_col)
                    
                    # найденного соседа по столбцу сохраним как точку
                    # для которой по строке мы также будем искать ненулевого соседа
                    local_point = neighbor_col

                    # выходим, так как нам нужен первый попавшийся сосед
                    break

    # возвращаем список вершин
    return pathloop

matrix = [
    [50, 0, 0, 0, 0],
    [0, 60, 0, 0, 40],
    [50, 10, 50, 40, 0]
]

# должен вывести: [(2, 2), (2, 0), (0, 0), (0, 2)]
# выводит: [(0, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2)]
# то есть в списке есть лишние точки: (2, 1), (1, 1)
# через которые цикл не должен проходить
print(find_cycle(matrix, (0, 2)))