Решение лабиринта с использованием стека в Python - мой алгоритм верен?

Question

Я написал некоторый код Python, чтобы помочь мне понять, как решить лабиринт, используя стек и без рекурсии.

то, что я придумал для работы с SEEMS (как в целевой позиции вДостигнут 2-ый массив, представляющий лабиринт - это несколько версий лабиринтаПредставление if 1 для стены, 0 для пробела, 2 для цели и 3 для "посещенных".

Однако я подозрительно и хотел бы, чтобы кто-то подтвердилправильна ли логика или нет, что мне нужно сделать, чтобы ее исправить.

Моя главная проблема заключается в том, чтобы координаты возвращались в стек, даже если они были посещены.

Пожалуйстапонять природу ситуации, в которой находится курица и яйцо - я не до конца понимаю, как работает алгоритм, поэтому я написал некоторый код, который поможет мне понять, но я не уверен, что код правильный, что отчасти зависит от пониманияАлгоритм ...

Как всегда, любая помощь высоко ценится.Код ниже:

class Stack:
    def __init__(self):
        self.list = []

    def push(self, item):
        self.list.append(item)

    def pop(self):
        return self.list.pop()

    def top(self):
        return self.list[0]

    def isEmpty(self):
        return not self.list

    def empty(self):
        self.list = []

maze = [[0, 0, 1, 1],
        [0, 1, 0, 1],
        [0, 0, 1, 1],
        [0, 0, 2, 0]]

MAZE_SIZE = len(maze)


def print_maze(maze):
    for row in maze:
        print((row))

def is_valid_pos(tup):
    (col, row) = tup
    if col < 0 or row < 0 or col >= MAZE_SIZE  or row >= MAZE_SIZE :
        return False
    return maze[row][col] == 0 or maze[row][col] == 2


def solve(maze, start):
    s = Stack()
    (col,row) = start
    print('pushing ({},{})'.format(col,row))
    s.push((col,row))

    while not s.isEmpty():
        print('Stack contents: {}'.format(s.list))
        input('Press Enter to continue: ')
        print('Popping stack')
        (col, row) = s.pop()
        print('Current position: ({}, {})'.format(col,row))

        if maze[row][col] == 2:
            print('Goal reached at ({}, {})'.format(col,row))
            return
        if maze[row][col] == 0:
            print('Marking ({}, {})'.format(col,row))
            maze[row][col] = 3
        print_maze(maze)
        print('Pushing coordinates of valid positions in 4 directions onto stack.')
        if is_valid_pos((col+1, row)): s.push((col+1, row)) 
        if is_valid_pos((col, row+1)): s.push((col, row+1))
        if is_valid_pos((row, col-1)): s.push((row, col-1))
        if is_valid_pos((row-1, col)): s.push((row, col))


solve(maze, (0,0))

Answer 1

Поскольку в вашей системе координат столбцы всегда располагаются перед строками, вы должны изменить:

if is_valid_pos((row, col-1)): s.push((row, col-1))
if is_valid_pos((row-1, col)): s.push((row, col))

на:

if is_valid_pos((col-1, row)): s.push((col-1, row))
if is_valid_pos((col, row-1)): s.push((col, row-1))

, и ваш код будет работать.