五、问题：迷宫问题

5.1 方法一：用栈方法解决迷宫问题

class MyStack(object):
    """
    自定义栈类
    """

    def __init__(self):
        self.stack = []

    def push(self, data=None):
        """
        入栈
        :param data: 入栈数据
        :return:
        """
        self.stack.append(data)

    def pop(self):
        """
        出栈
        :return: 出栈数据
        """
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError('stack is empty!')

    def is_empty(self):
        """
        判断栈是否为空
        :return:
        """
        return len(self.stack) == 0

    def get_pop(self):
        """
        获取栈顶元素
        :return:
        """
        return self.stack[-1]

    def __str__(self):
        """
        字符串方法
        :return:
        """
        stack_str = ''
        for data in self.stack:
            stack_str += f' -> {data}'
        return stack_str[4:]


# 当前位置的下一步位置坐标
directions = [
    lambda x, y: (x - 1, y),
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1),
]


def maze_stack(maze, start_xy, end_xy):
    """
    用栈方法解决迷宫问题
    深度优先：把走过的路线坐标存入栈，一条路失败后，通过坐标出栈，逐个退回，再重新试探新的路线坐标
    :param maze: 迷宫矩阵
    :param start_xy: 起点坐标
    :param end_xy: 终点坐标
    :return:
    """
    path = MyStack()
    path.push(start_xy)
    while not path.is_empty():
        curr_xy = path.get_pop()  # 当前坐标
        if curr_xy == end_xy:  # 到达终点
            print(path)
            return True
        for direction in directions:  # 试探下一步
            next_xy = direction(curr_xy[0], curr_xy[1])
            if maze[next_xy[0]][next_xy[1]] == 0:  # 有路，把下一步的坐标push入栈
                path.push(next_xy)
                maze[next_xy[0]][next_xy[1]] = 1  # 走过的路标记为墙
                break
        else:  # 无路，把上一步的坐标pop出栈
            path.pop()
    else:
        print('无解')
        return False
    

5.2 方法二：用队列方法解决迷宫问题

class MyQueue(object):
    """
    自定义环形队列类
    """

    def __init__(self, size=100):
        self.size = size
        self.queue = [None for _ in range(size)]
        self.front = 0  # 首位下标
        self.rear = 0  # 末位下标

    def append(self, data=None):
        """
        末位入队列
        :param data: 入队数据
        :return:
        """
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = data
        else:
            raise IndexError('queue is filled!')

    def pop(self):
        """
        末位出队列
        :return: 出队数据
        """
        if not self.is_empty():
            self.rear = (self.rear - 1) % self.size
            return self.queue[self.rear]
        else:
            raise IndexError('queue is empty!')

    def appendleft(self, data=None):
        """
        首位入队列
        :param data: 入队数据
        :return:
        """
        if not self.is_filled():
            self.queue[self.front] = data
            self.front = (self.front - 1) % self.size
        else:
            raise IndexError('queue is filled!')

    def popleft(self):
        """
        首位出队列
        :return: 出队数据
        """
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError('queue is empty!')

    def is_empty(self):
        """
        判断队列是否为空
        :return:
        """
        return self.rear == self.front

    def is_filled(self):
        """
        判断队列是否已满
        :return:
        """
        return self.front == (self.rear + 1) % self.size

    def __str__(self):
        """
        字符串方法
        :return:
        """
        queue_str = ''
        if not self.is_empty():
            if self.rear > self.front:
                for i in range(self.front + 1, self.rear + 1):
                    queue_str += f' -> {self.queue[i]}'
            elif self.rear < self.front:  # rear和front跨过0号下标的情况
                for i in range(self.front + 1, self.size):
                    queue_str += f' -> {self.queue[i]}'
                for i in range(self.rear + 1):
                    queue_str += f' -> {self.queue[i]}'
        else:
            queue_str = ' -> NULL'
        return queue_str[4:]

      
# 当前位置的下一步位置坐标
directions = [
    lambda x, y: (x - 1, y),
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1),
]

      
def maze_queue(maze, start_xy, end_xy):
    """
    用队列方法解决迷宫问题
    广度优先：把每一个坐标的任意一个可以前进的下一步坐标，存入队列，并将当前坐标出队列存入历史路线，重复这种操作，直到达到终点坐标，路线也将是最短的路线
        为了能回溯路线到起点，需要在坐标进出队列操作时，同时也将该坐标与父坐标的指向关系传入
    :param maze: 迷宫矩阵
    :param start_xy: 起点坐标
    :param end_xy: 终点坐标
    :return:
    """
    q = MyQueue()
    path_flag = []
    start_gps = {  # GPS：坐标 + 与父坐标的指向关系
        'position': start_xy,
        'flag': -1,
    }
    q.append(start_gps)
    while not q.is_empty():
        curr_gps = q.popleft()
        path_flag.append(curr_gps)  # 路径追加GPS
        curr_xy = curr_gps.get('position')  # 当前坐标
        if curr_xy == end_xy:  # 到达终点
            print(real_path(path_flag))
            return True
        for direction in directions:  # 试探下一步
            next_xy = direction(curr_xy[0], curr_xy[1])
            if maze[next_xy[0]][next_xy[1]] == 0:  # 把所有能走的下一步GPS都存入队列
                next_gps = {
                    'position': next_xy,
                    'flag': len(path_flag) - 1,
                }
                q.append(next_gps)
                maze[next_xy[0]][next_xy[1]] = 1  # 走过的路标记为墙
    else:
        print('无解')
        return False
      

5.3 演示

from copy import deepcopy

the_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, 1],
        [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ]
    maze1 = deepcopy(the_maze)
    maze2 = deepcopy(the_maze)
    start = (1, 1)
    end = (8, 8)
    # 栈方法：深度优先
    maze_stack(maze1, start, end)
    # 队列方法：广度优先
    maze_queue(maze2, start, end)