Share This
Связаться со мной
Крути в низ
Categories
//Сможете ли вы выйти из лабиринта?

Сможете ли вы выйти из лабиринта?

19.11.2021Category : Python

Кодинг-марафон. Задача № 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:

smozhete li vy vyjti iz labirinta f584c84 - Сможете ли вы выйти из лабиринта?

""" Лабиринт """ 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. Визуализация:

smozhete li vy vyjti iz labirinta 9d66b78 - Сможете ли вы выйти из лабиринта?smozhete li vy vyjti iz labirinta 6ed99a1 - Сможете ли вы выйти из лабиринта?

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

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

Скачать ×

  • 4 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2022 / All rights reserved

    Связаться со мной
    Close