Пользователь
0,0
рейтинг
23 декабря 2014 в 13:00

Разработка → Алгоритм поиска пути в лабиринте и его реализация на 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()


Спасибо за прочтение, надеюсь, кому-то будет полезно.
@Hippskill
карма
1,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (14)

  • +1
    Прямо моя лаба, только не на C++, а на Python. Прослезился. Спасибо.
  • +2
    Вы пишете на Python так, как будто это C. :)

    Например,
     x2 = rdl[0]
     y2 = rdl[1]
    

    можно переписать вот так:
     x2, y2 = rdl[0], rdl[1]
    
    • +1
      Или даже как-то так:
      x2, y2, *tmp = rdl
      

      (Вместо tmp, естественно, можно что угодно подставить, хоть подчеркивание)
      • +1
        да хоть
        x2, y2 = rd1
        
        • 0
          Вначале я, конечно, хотел предложить подобное. Но кто ж разберет, что там отдали на поток ввода. Мой вариант совместим с исходным, где можно написать любое количество чисел. Понятно, что там в любом случае надо бы обработку вводить.
          • 0
            Спасибо за исправления, попутался улучшить, а также добавил, почему-то не загрузившуюся, картинку задачи.
  • +2
    На питоне можно и покороче и покрасивее написать. У вас не питон, а паскаль какой-то…
  • +4
    За что вы так с именами переменных то…
    • 0
      ну, лаба же!
      «wave» прикажете именовать? )
      • +2
        «volna» — еще терпимо.
        stroka = [] — это вот уже за гранью. с тем же успехом можно продолжить — spisok = ""; chislo = {}.
        про x1/x2 я даже говорить не буду.
      • +2
        Ну уже теплее)) Надо сразу привыкать давать грамотные названия переменным, классам и тд. А то потом это тяжело искоренять ;)
  • 0
    Только это не волновой алгоритм. Волновой это обход в ширину. Здесь же написан обход в глубину.
    Задачу нахождения пути решает, но путь может оказаться не кратчайшим.
    Прочитать можно, например, тут: bfs, dfs.
    • 0
      Путь является кратчайшим, т.к. в каждой ячейки лабиринта будет минимальные путь от выбранной ячейки, за счет этой проверки:
      (lab[x+1][y] != -1 and lab[x+1][y] > cur) 
      • 0
        Да, извините, не дочитал. В таком случае это просто будет работать в худшем случае O(n^2 m^2) вместо O(nm). Я понимаю, что в приведённой задаче ограничения небольшие, но попробуйте запустить эту программу на пустом поле 1000 на 1000 хотя бы.
        Ещё можно для интереса повыводить все новые значения в lab, чтобы увидеть, что тут что-то не так (это можно и в пустой таблице 5 на 5 сделать).
        Обход в ширину будет знать правильное расстояние для каждой посещённой вершины во время первого же посещения. Эта программа будет ходить по клеткам по многу раз улучшая текущий оптимальный ответ.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.