刚学python(使用堆栈的迷宫求解器 )lab不会写

img

img

img

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((col-1, row)): s.push((col-1, row))
        if is_valid_pos((col, row-1)): s.push((col, row-1))


solve(maze, (0,0))

maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
dirs = [
lambda x, y: (x, y + 1),
lambda x, y: (x + 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x - 1, y),
]

def maze_path_stack(x1, y1, x2, y2):
stack = []
stack.append((x1, y1)) # (x1, y1)是起点坐标,类型是元组
while len(stack) > 0:
# 将栈的最后元素作为当前节点
curNode = stack[-1]
# 判断当前节点是否是出口,是则打印出路径节点
if curNode[0] == x2 and curNode[1] == y2:
for path in stack:
print(path)
return True
# 不是则向四个方向前进
else:
# dir为当前节点的右下左上
for dir in dirs:
# 获取到下一个节点nextNode的坐标
nextNode = dir(curNode[0], curNode[1])
# 判断此节点是否可以走
if maze[nextNode[0]][nextNode[1]] == 0:
# 可以则将此节点入栈
stack.append(nextNode)
# 标记此节点已经走过
maze[nextNode[0]][nextNode[1]] = 2
# 找到一个节点能走后则跳出此for循环,回到28行:curNode = stack[-1]
break
# 此else与for循环对应,表示当前节点找不到下一个节点可以走
else:
# 将当前节点标记为走过
maze[nextNode[0]][nextNode[1]] = 2
# 将当前节点出栈,此时栈中最后一个元素为上一个节点
stack.pop()
# 执行此语句后跳回28行:curNode = stack[-1],
else: # 此else与while对应,表示从起点出发,找不到下一个可以走的节点
print('没有路')
return False

maze_path_stack(1, 1, 8, 8)
print(maze)