N
Here's the decision. Python And no class. He's also writing an adventure story. :(The first option was beautiful, but not entirely under the task. Now it's kind of like a solution to the assignment.)The basic principle of algorithm is that we go to the right first. If we found the key, we'll keep the situation in the glass, so we can try to get left in case the right path fails. If we're right, we're getting a fortune out of the grid, and we're trying to get left. If we go left and find the key, then the algorithm repeats itself. Until we either get out or the glass of the creature will not devastate (i.e., all the keys found are tested, and the new keys cannot be reached).If there's no way out, path contains the shortest way to kill, and path of the last element max_stack - the longest.DOOR_LOCKED = 'D'
DOOR_OPENED = 'd'
PLAYER = 'G'
KEY = 'K'
EMPTY = '.'
LEFT = -1
RIGHT = +1
DIRS = {RIGHT: '>>> Пойду направо', LEFT: '<<< Пойду налево'}
def solve(_maze, _print_path=False):
maze = list(_maze)
pos = maze.index(PLAYER)
keys = 0
dir = RIGHT
path = []
maze[pos] = EMPTY
stack = [(maze[:], pos, keys, path[:])]
max_stack = stack[:]
while pos not in (-1, len(maze)):
if DOOR_LOCKED == maze[pos]:
if keys:
keys -= 1
maze[pos] = DOOR_OPENED
path.append(f" Дверь. Открываю. Осталось ключей: {keys}.")
elif stack:
maze, pos, keys, path = stack.pop()
dir = LEFT
else:
maze, pos, keys, path = max_stack.pop()
path.append(" Ключей больше нет. Я здесь умру! :(")
if _print_path:
print(_maze, "\nMoё смертельное приключение:\n"+"\n".join(path)+"\n")
return False
elif KEY == maze[pos]:
keys += 1
maze[pos] = EMPTY
path.append(f" Нашёл ключ. Стало ключей: {keys}.")
stack.append((maze[:], pos, keys, path[:]))
if len(stack) > len(max_stack): max_stack = stack[:]
dir = RIGHT
maze_tmp = maze[:]
maze_tmp[pos] = "*"
path.append("".join(maze_tmp) + " | " + DIRS[dir])
pos += dir
path.append(f"Ура! Я таки вышел! Осталось ключей: {keys}.")
if _print_path:
print(_maze, "\nMoё успешное приключение:\n"+"\n".join(path)+"\n")
return True
mazes = ["DKDDGKKDDKDD", "DDKGDDKKKKKKD", "DDDDKKKDDKGDKKDDD", "DDKGKDD", "DDDKGKDDKDD" ]
for maze in mazes:
print(maze, "=>", "Ура! Выход есть!" if solve(maze, False) else "Увы. Выхода нет.")
#maze = "DDDDDDDDDKKDKKDKKDDDKGDKKKDDKDDKDDKD"
#maze = "DDDDDDDDDKKDKKDKKDDDKGDKKKDDKDDKDDKDDDDDDD"
for maze in ["DDGKKDKDDD", "DDDKDDKKGDKKDDDD"]:
print(maze, "=>", "Ура! Выход есть!" if solve(maze, True) else "Увы. Выхода нет.", "\n")
DKDDGKKDDKDD => Ура! Выход есть!
DDKGDDKKKKKKD => Увы. Выхода нет.
DDDDKKKDDKGDKKDDD => Ура! Выход есть!
DDKGKDD => Ура! Выход есть!
DDDKGKDDKDD => Увы. Выхода нет.
DDGKKDKDDD
Moё успешное приключение:
DDKKDKDDD | >>> Пойду направо
Нашёл ключ. Стало ключей: 1.
DD.KDKDDD | >>> Пойду направо
Нашёл ключ. Стало ключей: 2.
DD..DKDDD | >>> Пойду направо
Дверь. Открываю. Осталось ключей: 1.
DD...KDDD | >>> Пойду направо
Нашёл ключ. Стало ключей: 2.
DD...dDDD | <<< Пойду налево
DD....DDD | <<< Пойду налево
DD..d.DDD | <<< Пойду налево
DD..d.DDD | <<< Пойду налево
DD..d.DDD | <<< Пойду налево
Дверь. Открываю. Осталось ключей: 1.
D...d.DDD | <<< Пойду налево
Дверь. Открываю. Осталось ключей: 0.
*d...d.DDD | <<< Пойду налево
Ура! Я таки вышел! Осталось ключей: 0.
DDGKKDKDDD => Ура! Выход есть!
DDDKDDKKGDKKDDDD
Moё смертельное приключение:
DDDKDDKKDKKDDDD | <<< Пойду налево
Нашёл ключ. Стало ключей: 1.
DDDKDDK.DKKDDDD | >>> Пойду направо
DDDKDDK.DKKDDDD | >>> Пойду направо
Дверь. Открываю. Осталось ключей: 0.
DDDKDDK..KKDDDD | >>> Пойду направо
Нашёл ключ. Стало ключей: 1.
DDDKDDK..dKDDDD | >>> Пойду направо
Нашёл ключ. Стало ключей: 2.
DDDKDDK..d.DDDD | <<< Пойду налево
DDDKDDK..d.DDDD | <<< Пойду налево
DDDKDDK....DDDD | <<< Пойду налево
DDDKDDK.d..DDDD | <<< Пойду налево
DDDKDDK.d..DDDD | <<< Пойду налево
Нашёл ключ. Стало ключей: 3.
DDDKDD*..d..DDDD | >>> Пойду направо
DDDKDD..d..DDDD | >>> Пойду направо
DDDKDD..d..DDDD | >>> Пойду направо
DDDKDD.....DDDD | >>> Пойду направо
DDDKDD...d.DDDD | >>> Пойду направо
DDDKDD...d.DDDD | >>> Пойду направо
Дверь. Открываю. Осталось ключей: 2.
DDDKDD...d..DDD | >>> Пойду направо
Дверь. Открываю. Осталось ключей: 1.
DDDKDD...d..dDD | >>> Пойду направо
Дверь. Открываю. Осталось ключей: 0.
DDDKDD...d..ddD | >>> Пойду направо
Ключей больше нет. Я здесь умру! :(
DDDKDDKKGDKKDDDD => Увы. Выхода нет.