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

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

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

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

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

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

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

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, m = rdl
    for i in range(n):
        rdl = input()
        cur = []
        for k in range(m):
            if int(rdl[k]) == 1:
                cur.append(-1)   
            else:    
                cur.append(int(rdl[k]))
        lab.append(cur)
    rdl = list(map(int,input().split()))
    x1, y1 = rdl[0]-1, rdl[1]-1
    rdl = list(map(int,input().split()))
    x2, y2 = rdl[0]-1, rdl[1] -1
    lab = voln(x1,y1,1,n,m,lab)
    if lab[x2][y2] > 0:
        print("Mozhet")
    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()

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

 x2 = rdl[0]
 y2 = rdl[1]

 x2, y2 = rdl[0], rdl[1]

x2, y2, *tmp = rdl

x2, y2 = rd1

(lab[x+1][y] != -1 and lab[x+1][y] > cur)