Как найти путь между двумя случайными точками в матрице 0 и 1

Question

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

Мне нужен этот метод, чтобы дать мне представление о пути, по которому следует идти, например:

пример

Где возврат будет «вправо, вверх, вправо, вправо, вниз, вправо» и «вниз, вправо, вниз, вправо, вправо, вверх, вправо, вверх» соответственно.

Спасибо

Answer 1

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

dest_x = 4
dest_y = 1
visited = []

def next (path, x, y):
    visited.append ([x, y])
    
    # obstacle
    if matrix[x][y] == 0:
        return None
    
    # found destination
    if x == dest_x and y == dest_y:
        return path
    
    for i in [{'x': x - 1, 'y': y, 'direction': 'left'},
              {'x': x + 1, 'y': y, 'direction': 'right'},
              {'x': x, 'y': y - 1, 'direction': 'up'},
              {'x': x, 'y': y + 1, 'direction': 'down'}]:
        if [i['x'], i['y']] not in visited and i['x'] >= 0 and i['x'] < len(matrix) and i['y'] >= 0 and i['y'] < len(matrix[x]):
            n = next (path + [i['direction']], i['x'], i['y'])
            if n != None:
                return n
    
    
    

matrix = [[1,1,1,1],
          [1,1,1,1],
          [1,0,0,1],
          [1,1,1,1],
          [1,1,1,1]]

print (next ([], 0, 1))

Это найдет один путь, если он есть. Если вам нужен кратчайший путь, вы можете сохранить путь в массиве по достижении пункта назначения вместо его возврата. Когда все пути обнаружены, вы можете распечатать путь минимальной длины