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

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

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

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]