Алгоритм поиска пути в лабиринте и его реализация на Python 3.4

в 10:00, , рубрики: python, python3, алгоритм, Спортивное программирование

Недавно для решения задачи о прохождении лабиринта, которых, кстати, не мало, я решил воспользоваться «волновым алгоритмом», о котором ранее мне приходилось слышать. К моему сожаления, найти внятное объяснение его работы с примерами реализации на нужном мне языке не получилось, следствием чего является эта статья.

Итак, будем пытаться написать его самостоятельно, а для этого нужно продумать, как он должен работать. Для этого возьмём достаточно легкую задачу:

Алгоритм поиска пути в лабиринте и его реализация на Python 3.4 - 1

  1. Для начала разберемся с входными данными: у нас есть матрица элементов, где 0 — пустые клетки, а 1 — стенки.
  2. При вводе меняем «1» на "-1" (этого требует алгоритм)
  3. Далее нужно выбрать ячейку, с которой начнется обход
  4. Рекурсивно обойти лабиринт от выбранной ячейки, вставляя в ячейку текущий «уровень волны»

Ввод данных будет выглядеть следующим образом:

rdl = list(map(int,input().split()))
n = rdl[0]
m = rdl[1]
for i in range(n):
        rdl = input()
        stroka = []
        for k in range(m):
            if int(rdl[k]) == 1:
                stroka.append(-1)   
            else:    
                stroka.append(int(rdl[k]))
        lab.append(stroka)

Теперь у нас есть двумерная матрица, представляющая наш лабиринт.
Далее нам нужно написать функцию, которая будет обходить наш лабиринт:

def voln(x, y, cur, n, m, lab):

Где x, y — координаты текущей ячейки; cur — «уровень волны»; n, m — размеры лабиринта; lab — сам лабиринт.
Для начало нужно заполнить текущую ячейку уровнем воды:

lab[x][y] = cur

Далее проверим, есть ли у нас возможность «пойти» влево:

if y+1 < m:

Если есть такая возможность, то проверяем, нет ли там стенки или текущий «уровень воды» меньше, чем в ячейке справа :

if lab[x][y+1] == 0 or (lab[x][y+1] != -1 and lab[x][y+1] > cur):

И в случае «успеха» рекурсивно идем вправо:

voln(x,y+1,cur+1,n,m,lab)

Теперь нужно точно также проверить возможность пройти вниз, влево и вверх:

if x+1<n:
    if lab[x+1][y] == 0 or (lab[x+1][y] != -1 and lab[x+1][y] > cur):
            voln(x+1,y,cur+1,n,m)
if x-1>=0:
    if lab[x-1][y] == 0 or (lab[x-1][y] != -1 and lab[x-1][y] > cur):
            voln(x-1,y,cur+1,n,m)
if y-1>=0:
    if lab[x][y-1] == 0 or (lab[x][y-1] != -1 and lab[x][y-1] > cur):
            voln(x,y-1,cur+1,n,m)

Все, осталось в конце вернуть текущий лабиринт:

return lab

Готовая программа:

def main():
    lab = []
    rdl = list(map(int,input().split()))
    n = rdl[0]
    m = rdl[1]
    for i in range(n):
        rdl = input()
        stroka = []
        for k in range(len(rdl)):
            if int(rdl[k]) == 1:
                stroka.append(-1)   
            else:    
                stroka.append(int(rdl[k]))
        lab.append(stroka)
    rdl = list(map(int,input().split()))
    x1 = rdl[0] -1
    y1 = rdl[1] -1
    rdl = list(map(int,input().split()))
    x2 = rdl[0]
    y2 = rdl[1]
    lab = voln(x1,y1,1,n,m,lab)
    if lab[x2][y2] > 0:
        print("Mozhet")
        for i in range(len(finalout)):
            print(finalout[i], end="")
    else:
        print("Ne mozhet")    
def voln(x,y,cur,n,m):
    lab[x][y] = cur
    if y+1<m:
        if lab[x][y+1] == 0 or (lab[x][y+1] != -1 and lab[x][y+1] > cur):
            voln(x,y+1,cur+1,n,m,lab)
    if x+1<n:
        if lab[x+1][y] == 0 or (lab[x+1][y] != -1 and lab[x+1][y] > cur):
            voln(x+1,y,cur+1,n,m,lab)
    if x-1>=0:
        if lab[x-1][y] == 0 or (lab[x-1][y] != -1 and lab[x-1][y] > cur):
            voln(x-1,y,cur+1,n,m,lab)
    if y-1>=0:
        if lab[x][y-1] == 0 or (lab[x][y-1] != -1 and lab[x][y-1] > cur):
            voln(x,y-1,cur+1,n,m,lab)
    return lab
main()

Спасибо за прочтение, надеюсь, кому-то будет полезно.

Автор: Hippskill

Источник


  1. петр:

    Здравствуйте!
    а можно пример входных и выходных данных?

  2. Александр:

    finalout – это что??

  3. Ирина:

    lab = voln(x1,y1,1,n,m,lab)
    надо заменить на:
    finalout = voln(x1,y1,1,n,m,lab)

  4. Екатерина:

    Спасибо большое!!! Очень сильно помогло.
    Если кому нужно то для восстановлении пути понадобится такая функция
    def way(x1, y1, x2, y2, lab):
    path = [[0] * m for _ in range(n)]
    path[y2][x2] = 1
    while (x1, y1) != (x2, y2):
    if self.check(x2 – 1, y2) and lab[y2][x2 – 1] == lab[y2][x2] – 1:
    x2, y2 = x2 – 1, y2
    elif self.check(x2 + 1, y2) and lab[y2][x2 + 1] == lab[y2][x2] – 1:
    x2, y2 = x2 + 1, y2
    elif self.check(x2, y2 – 1) and lab[y2 – 1][x2] == lab[y2][x2] – 1:
    x2, y2 = x2, y2 – 1
    elif self.check(x2, y2 + 1) and lab[y2 + 1][x2] == lab[y2][x2] – 1:
    x2, y2 = x2, y2 + 1
    path[y2][x2] = 1
    return path

    x1, y1 – начальные координаты
    x2, y2 – конечные координаты
    lab – результат работы функции автора данной статьи
    n, m – размерность массива
    Функция возвращает двумерный массив, заполненный 0 и 1. Где 1 – ячейка, в которой должен побывать игрок

  5. Дмитрий и Олег:

    В данной реализации волнового алгоритма ужасно все. Но особенно меня тревожит и пугает рекурсия, которая бесконечно медленно обрабатывает поле. Возьмем к примеру поле 13 на 13. Он обработает его секунд за 10. Для какого-нибудь проекта, в котором необходимо быстро обрабатывать поле, данный метод реализации точно не подойдет. Также из минусов можно отметить то, что программа представленная в статье находится в нерабочем состоянии – рекурсия вызывает себя с 6-ю аргументами, а принимает только 5. К тому же автор не разбирается в среде разработки – в данную функцию можно передавать всего 3, а то и меньше, аргумента. Приведу свой пример функции:

    def to_wave_board(x, y, lab):
    sp = [(x, y)]
    cur = 0
    while sp != []:
    cur += 1
    sp1 = []
    for el in sp:
    point = lab[el[1]][el[0]]
    if point == 0:
    lab[el[1]][el[0]] = cur
    try:
    if lab[el[1] + 1][el[0]] == 0:
    sp1.append((el[0], el[1] + 1))
    except Exception:
    pass
    try:
    if el[1] – 1 > -1 and lab[el[1] – 1][el[0]] == 0:
    sp1.append((el[0], el[1] – 1))
    except Exception:
    pass
    try:
    if lab[el[1]][el[0] + 1] == 0:
    sp1.append((el[0] + 1, el[1]))
    except Exception:
    pass
    try:
    if el[0] – 1 > -1 and lab[el[1]][el[0] – 1] == 0:
    sp1.append((el[0] – 1, el[1]))
    except Exception:
    pass
    sp = list(set(sp1))
    return lab

    Данный вариант кода в РАЗЫ быстрее обрабатывает лабиринт.

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js