Кодинг-марафон. Задача № 10.

Лабиринт может быть представлен двухмерной матрицей, где нули представляют области, по которым можно ходить, а единицы — стены. Вы начинаете движение с верхнего левого угла, а выход находится в самой нижней правой ячейке.

Создайте функцию, которая возвращает истину, если пройти лабиринт от одного конца до другого возможно. Двигаться можно только вверх, вниз, влево и вправо. По диагонали двигаться нельзя.

Примеры

can_exit([   [0, 1, 1, 1, 1, 1, 1],   [0, 0, 1, 1, 0, 1, 1],   [1, 0, 0, 0, 0, 1, 1],   [1, 1, 1, 1, 0, 0, 1],   [1, 1, 1, 1, 1, 0, 0] ]) ➞ true  can_exit([   [0, 1, 1, 1, 1, 1, 1],   [0, 0, 1, 0, 0, 1, 1],   [1, 0, 0, 0, 0, 1, 1],   [1, 1, 0, 1, 0, 0, 1],   [1, 1, 0, 0, 1, 1, 1] ]) ➞ false # В этом лабиринте одни тупики!  can_exit([   [0, 1, 1, 1, 1, 0, 0],   [0, 0, 0, 0, 1, 0, 0],   [1, 1, 1, 0, 0, 0, 0],   [1, 1, 1, 1, 1, 1, 0],   [1, 1, 1, 1, 1, 1, 1] ]) ➞ false # Выход так близко, но недостижим!  can_exit([   [0, 1, 1, 1, 1, 0, 0],   [0, 0, 0, 0, 1, 0, 0],   [1, 1, 1, 0, 0, 0, 0],   [1, 0, 0, 0, 1, 1, 0],   [1, 1, 1, 1, 1, 1, 0] ]) ➞ true

Примечание: в лабиринте размером m x n вы входите в [0, 0] и выходите в [m-1, n-1].

Решение

def can_exit(lst):     def step(x, y):         if 0<=x<len(lst[0]) and 0<=y<len(lst) and lst[y][x] == 0:             lst[y][x] = 2             for dx, dy in ((0,-1), (0,1), (-1,0), (1,0)):                 step(x+dx, y+dy)     step(0, 0)     return lst[-1][-1] == 2

Решения с визуализациями от участников марафона

Решение vvia vvia:

""" Лабиринт """ import copy from tkinter import * from tkinter.messagebox import showinfo from random import randint import time # Функция считает для каждого слота возможные пути def count_mine(mine_map_end): while True: temp = copy.deepcopy(mine_map_end) for row in range(0, ROW): for col in range(0, COLUMNS): # Проверяем что записано в текущем слоте на котором мы 'стоим' k = mine_map_end[row][col] # Если мы находимся на слоте который стена или на слоте который пустой(кроме начального) # то пропускаем эту итерацию цикла. if mine_map_end[row][col] == 'X' or (k == 0 and row + col != 0): continue # Перебираем смещения(по строкам и столбцам) относительно слота где мы стоим. for (dx, dy) in (0, 1), (1, 0), (-1, 0), (0, -1): # Проверяем не выходит ли соседний слот за границы матрицы. if any((col+dx < 0, col+dx > COLUMNS - 1, row+dy < 0, row+dy > ROW-1, (row+dy == 0 and col+dx == 0))): continue # Проверяем не является ли соседний слот стеной и нет там ли цифры кроме нуля. if mine_map_end[row + dy][col + dx] != 'X' and mine_map_end[row + dy][col + dx] == 0: # Прибавляем в соседний слот 1(по умолч там 0) mine_map_end[row + dy][col + dx] = k + 1 return mine_map_end if mine_map_end == temp else count_mine(mine_map_end) def output_exit(mine_map_end, buttons): way_exit = [] path_end = tuple() max_step = 0 # Выводим в слоты рассчитанные значения шагов для каждого слота(для отладки) for ind_row, row in enumerate(mine_map_end): for ind_col, col in enumerate(row): buttons[ind_row][ind_col].config(text=col) if type(col) is int: if col > max_step: max_step = col path_end = ((ind_row, ind_col)) if not path_end: buttons[0][0].config(bg='Red') return if mine_map_end[ROW-1][COLUMNS-1] == 0 or mine_map_end[ROW-1][COLUMNS-1] == 'X': way_exit.append((path_end[0], path_end[1])) max_count_step = max_step exit_map = False else: max_count_step = mine_map_end[ROW-1][COLUMNS-1] path_end = ((ROW-1, COLUMNS-1)) way_exit.append((path_end[0], path_end[1])) exit_map = True row = path_end[0] col = path_end[1] for current_step in range(max_count_step, -1, -1): color = 'Green' if exit_map else 'Red' buttons[row][col].config(bg=color) for (dx, dy) in (0, 1), (1, 0), (-1, 0), (0, -1): # Проверяем не выходит ли соседний слот за границы матрицы. if any((col+dx < 0, col+dx > COLUMNS-1, row+dy < 0, row+dy > ROW-1)): continue if mine_map_end[row+dy][col+dx] == current_step-1: way_exit.append((row+dy, col+dx)) row = row + dy col = col + dx buttons[ROW-1][COLUMNS-1].config(font='Calibre 9 bold', text='exit', fg='Red') buttons[0][0].config(text='start', fg='Blue') def click_on_button_start(mine_map, buttons, btn_help, btn_next): output_exit(count_mine(mine_map), buttons) btn_help.config(state=DISABLED) btn_next.config(state=NORMAL) # Функция создания случайным образом лабиринта. # Генерируем матрицу(двухмерный список) со случайными высотой и длиной(в зависимости от сложности игры), # со случайным количеством и расположением "стен" в матрице. def generator_map(): # Случайная высота и длина матрицы (карты лабиринта) row = columns = randint(7, 15) # Непосредственно генерируем матрицу в которой расставляем случайным образом # (застены, записываем в эти слоты '#'), в остальных слотах записываем '0'. mine_map = [[0 if randint(0, 100) > 25 else 'X' for j in range(0, columns)] for i in range(0, row)] mine_map[0][0] = 0 # Возвращаем сгенерированное поле. return mine_map # Главная функция MINEMAP() def MINEMAP() -> None: # Формируем игровое окно window = Tk() window.title('Лабиринт') # Создаем меню main_menu = Menu(window) window.config(menu=main_menu) main_menu.add_command(label='Выход', command=quit) main_menu.add_separator() # Создаем две рамки (Frame) в которую поместим упаковщиком pack() виджеты - надписи(label) и # кнопки(Button) для перебора "минных карт" и кнопку "HELP" frame = Frame() frame.pack(side=TOP, fill=X, expand=True) Label(frame, text=f'{40 * " "}ЛАБИРИНТ{40 * " "}', font='Arial 11').pack(pady=3) frame = Frame() frame.pack(side=TOP) btn_next = Button(frame, state=DISABLED, text="Next map", font='Calibre 10 bold', command=window.destroy) btn_next.grid(row=0, column=0, padx=50, pady=5) btn_help = Button(frame, text=" START ") btn_help.config(font='Calibre 10 bold', command=lambda: click_on_button_start(MINE_MAP, buttons, btn_help, btn_next)) btn_help.grid(row=0, column=1, padx=50, pady=5) # Создаем новую рамку (Frame) в которую поместим упаковщиком grid() матрицу из кнопок которая # и будет нам картой. frame = Frame() frame.pack(side=TOP) # В этом списке будем хранить объекты кнопок(матрица) buttons = [] for rows in range(ROW): temp = [] for col in range(COLUMNS): # Под каждый слот матрицы создаем экземпляр кнопки (каждая кнопка имеет определенный цвет фона). btn = Button(frame) btn.config(bd=1, width=3, height=1, font='Calibre 9 bold') if MINE_MAP[rows][col] == 'X': btn.config(activebackground='Red', text='X', bg='Black', fg='Red') else: btn.config(activebackground='White', bg='White', fg='Black') temp.append(btn) # формируем строку из объектов кнопок для матрицы btn.grid(row=rows, column=col) # упаковываем кнопки во фрейм упаковщиком grid() buttons.append(temp) # добавляем в матрицу строку из объектов кнопок buttons[ROW-1][COLUMNS-1].config(text='exit', fg='Red') buttons[0][0].config(text='start', fg='Blue') Label(frame, height=4, fg="White").grid(row=ROW, column=COLUMNS-1) # делаем отступ для карты снизу # Размещаем наше графич. окно в центре, для этого нужно высчитать размеры окна после # размещения на ней всех виджетов(оно каждый раз будет новым в зависимости от размера матрицы). # Обновляем окно когда все элементы размещены(чтобы высчитать его размер). window.update_idletasks() # Рассчитываем размеры окна s = window.geometry() # 384x405+104+104 # полные параметры окна(размеры 384x405 и начало координат +104+104) s = s.split('+') # ['384x405', '104', '104'] # отделяем размеры окна от начало координат s = s[0].split('x') # ['384', '405'] - вычленяем отдельно размеры(ширину и высоту) сформированного окна width_window = int(s[0]) # Ширина окна height_window = int(s[1]) # Высота окна # Размещаем наше графич. окно в центре экрана. x_start = (window.winfo_screenwidth() - width_window) // 2 # высчитываем начало окна по горизонтали y_start = (window.winfo_screenheight() - height_window) // 2 # высчитываем начало окна по вертикали # window.wm_geometry(f'+{0}+{0}') # выводим окно с верхнего левого угла (0,0) window.wm_geometry(f'+{x_start}+{y_start}') # выводим окно в центре window.resizable(width=False, height=False) # можно запретить изменять окно размеры mainloop() # Запускается основная программа if __name__ == "__main__": # Генерируем разные матрицы покуда не выберем 'Выход' из программы while True: # Вызываем функцию генерирования поля. MINE_MAP = generator_map() ROW = len(MINE_MAP) COLUMNS = len(MINE_MAP[0]) # Вызываем функцию окна. MINEMAP() 

Решение @danil0ff можно посмотреть на GitHub. Визуализация:

Марк Лутц «Изучаем Python»

Скачивайте книгу у нас в телеграм

Скачать ×