Недавно для решения задачи о прохождении лабиринта, которых, кстати, не мало, я решил воспользоваться «волновым алгоритмом», о котором ранее мне приходилось слышать. К моему сожаления, найти внятное объяснение его работы с примерами реализации на нужном мне языке не получилось, следствием чего является эта статья.
Итак, будем пытаться написать его самостоятельно, а для этого нужно продумать, как он должен работать. Для этого возьмём достаточно легкую задачу:
- Для начала разберемся с входными данными: у нас есть матрица элементов, где 0 — пустые клетки, а 1 — стенки.
- При вводе меняем «1» на "-1" (этого требует алгоритм)
- Далее нужно выбрать ячейку, с которой начнется обход
- Рекурсивно обойти лабиринт от выбранной ячейки, вставляя в ячейку текущий «уровень волны»
Ввод данных будет выглядеть следующим образом:
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
Здравствуйте!
а можно пример входных и выходных данных?
finalout – это что??
lab = voln(x1,y1,1,n,m,lab)
надо заменить на:
finalout = voln(x1,y1,1,n,m,lab)
Спасибо большое!!! Очень сильно помогло.
Если кому нужно то для восстановлении пути понадобится такая функция
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 – ячейка, в которой должен побывать игрок
В данной реализации волнового алгоритма ужасно все. Но особенно меня тревожит и пугает рекурсия, которая бесконечно медленно обрабатывает поле. Возьмем к примеру поле 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
Данный вариант кода в РАЗЫ быстрее обрабатывает лабиринт.