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


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

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.