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

Кодинг-марафон. Задача № 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. Визуализация: