Лабиринт с N дверями и 1 ключом

28.12.2019Backtracking, Динамическое программирование, Матрицы, Рекурсия

Учитывая N * N бинарный лабиринт, где 0 означает, что позиция может быть посещена, а 1 означает, что позиция не может быть посещена без ключа, задача состоит в том, чтобы найти, возможно ли посетить нижнюю правую ячейку сверху левая ячейка с одним ключом по пути. Если возможно, тогда напечатайте «Да», иначе напечатайте «Нет» .

Пример:

Input: maze[][] = {
{0, 0, 1},
{1, 0, 1},
{1, 1, 0}}
Output: Yes

Подход: эта проблема может быть решена с помощью рекурсии , для очень возможного перемещения, если текущая ячейка равна 0, тогда без изменения состояния клавиши проверьте, является ли это место назначения, иначе движение вперед. Если текущая ячейка равна 1, тогда ключ должен использоваться, теперь для дальнейших перемещений ключ будет установлен в значение false, то есть он никогда больше не будет использоваться по тому же пути. Если какой-либо путь достигает пункта назначения, выведите « Да», иначе выведите « Нет» .

Ниже приведена реализация вышеуказанного подхода:

# Python3 реализация подхода

# Рекурсивная функция для проверки наличия
# путь от верхней левой ячейки к
# нижняя правая ячейка лабиринта

def findPath(maze, xpos, ypos, key):

# Проверьте, является ли текущая ячейка

# в лабиринте

if xpos < 0 or xpos >= len(maze) or ypos < 0 \

or ypos >= len(maze):

return False

# Если ключ требуется, чтобы двигаться дальше

if maze[xpos][ypos] == '1':

# Если ключ ранее не использовался

if key == True:

# Если текущая ячейка является пунктом назначения

if xpos == len(maze)-1 and ypos == len(maze)-1:

return True

# Либо идти вниз, либо вправо

return findPath(maze, xpos + 1, ypos, False) or \

findPath(maze, xpos, ypos + 1, False)

# Ключ использовался ранее

return False

# Если текущая ячейка является пунктом назначения

if xpos == len(maze)-1 and ypos == len(maze)-1:

return True

# Либо идти вниз, либо вправо

return findPath(maze, xpos + 1, ypos, key) or \

findPath(maze, xpos, ypos + 1, key)

def mazeProb(maze, xpos, ypos):

key = True

if findPath(maze, xpos, ypos, key):

return True

return False

# Код драйвера

if __name__ == "__main__":

maze = [['0', '0', '1'],

['1', '0', '1'],

['1', '1', '0']]

n = len(maze)

# Если есть путь от ячейки (0, 0)

if mazeProb(maze, 0, 0):

print("Yes")

else:

print("No")

Выход:

Yes

Сложность времени: O (2 ^N )

Рекомендуемые посты:

Лабиринт с N дверями и 1 ключом

0.00 (0%) 0 votes