数据结构与算法分析2 Python解决牛郎织女迷宫问题

import numpy as np
import random


# 创建结点类
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


# 创建链栈
class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    # 判断栈是否非空
    def isEmpty(self):
        if self.top == None:
            return True
        else:
            return False

    # 将数据存入栈
    def Push(self, data):
        NewNode = Node(data)

        if self.top == None:
            self.top = NewNode
        else:
            NewNode.next = self.top
            self.top = NewNode
        self.size += 1

    # 删除最后进来的数据
    def Pop(self):
        if self.isEmpty():
            print("栈空无法出栈")
            return -1
        else:
            temp = self.top
            self.top = temp.next
            self.size -= 1
            return temp.data

    # 获取栈中数组长度
    def getLength(self):
        return self.size

    # 遍历栈
    def Travel(self):
        if self.isEmpty():
            print("栈空，无法遍历")
            return -1
        else:
            curse = self.top
            while curse != None:
                print(curse.data, end='')
                curse = curse.next
            print("")

    def getElement(self, position):
        if self.isEmpty():
            print("栈空，无法遍历")
            return -1
        elif position < 0 or position > self.getLength():
            print("位置越界")
        else:
            curse = self.top
            pos=self.getLength()-1
            while position != pos:
                curse = curse.next
                pos -= 1
            print(curse.data)


# 创建8*8的迷宫（包含四周边界故为10*10）
maze = np.zeros((10, 10))
# 迷宫边界四周的值均为-1
maze[0, :] = maze[9, :] = [-1] * 10
maze[:, 0] = maze[:, 9] = [-1] * 10
# 迷宫的障碍物
maze[1, 2] = maze[3, 7] = maze[5, 5] = maze[4, 4] = maze[8, 2] = -1

# [i1,j1]为起始坐标，[i2,j2]为终止坐标
i1 = j1 = i2 = j2 = 0
# 初始化坐标点：只要起点与终点不重合并且起点终点不在障碍物上即可
while i1 == i2 and j1 == j2 and not (
        [i1, j1] == [1, 2] and [i1, j1] == [3, 7] and [i1, j1] == [5, 5] and [i1, j1] == [4, 4] and [i1, j1] == [8, 2]
        and [i2, j2] == [1, 2] and [i2, j2] == [3, 7] and [i2, j2] == [5, 5] and [i2, j2] == [4, 4] and [i2, j2] == [8,
                                                                                                                     2]):
    i1 = random.randint(1, 8)
    j1 = random.randint(1, 8)
    i2 = random.randint(1, 8)
    j2 = random.randint(1, 8)
print("起点为{0}，终点为{1}".format([i1, j1], [i2, j2]))

# 初始化stack为链栈类
stack = Stack()


# 向下移动：若下方值不为-1即可移动，移动后将已经走过的路径变为-1以减少步长。后面的方法相同
def Down(i1, j1):
    if maze[i1 + 1, j1] != -1:
        maze[i1, j1] = -1
        stack.Push([i1, j1])
        return [i1 + 1, j1]
    else:
        return [i1, j1]


def Up(i1, j1):
    if maze[i1 - 1, j1] != -1:
        maze[i1, j1] = -1
        stack.Push([i1, j1])
        return [i1 - 1, j1]
    else:
        return [i1, j1]


def Left(i1, j1):
    if maze[i1, j1 - 1] != -1:
        maze[i1, j1] = -1
        stack.Push([i1, j1])
        return [i1, j1 - 1]
    else:
        return [i1, j1]


def Right(i1, j1):
    if maze[i1, j1 + 1] != -1:
        maze[i1, j1] = -1
        stack.Push([i1, j1])
        return [i1, j1 + 1]
    else:
        return [i1, j1]


while not (i1 == i2 and j1 == j2):
    # 若上下左右均为-1，此时回溯
    if maze[i1 + 1, j1] == -1 and maze[i1 - 1, j1] == -1 and maze[i1, j1 + 1] == -1 and maze[i1, j1 - 1] == -1:
        maze[i1, j1] = -1
        [i1, j1] = stack.Pop()
    # 由于我想要得到最短的路径，因此我采用根据概率的方法尝试将路径缩短
    # 概率的计算方法如下：若终点在起点上i个格子，右j个格子：
    # 则点向上走的概率为(i+1)/(i+1)+(j+1)+1+1，向下走的概率为1/(i+1)+(j+1)+1+1
    # 向左走的概率为1/(i+1)+(j+1)+1+1，向右走的概率为(j+1)/(i+1)+(j+1)+1+1
    else:
        if i1 < i2:
            up_pro = 1  # 向上走的权值
            down_pro = i2 - i1 + 1  # 向下走的权值
            if j1 < j2:
                left_pro = 1  # 向左走的权值
                right_pro = j2 - j1 + 1  # 向右走的权值
            else:
                right_pro = 1
                left_pro = j1 - j2 + 1
        else:
            down_pro = 1
            up_pro = i1 - i2 + 1
            if j1 < j2:
                left_pro = 1
                right_pro = j2 - j1 + 1
            else:
                right_pro = 1
                left_pro = j1 - j2 + 1
        # 权值计算完毕，总的权值和即为所有相加
        total = up_pro + down_pro + right_pro + left_pro
        # 随机生成1-total的整数值，并且按照权值分配给向某个方向走的概率，以尽量使得总路径长度最短
        rand = random.randint(1, total)
        if rand >= 1 and rand < 1 + right_pro:
            [i1, j1] = Right(i1, j1)
        elif rand >= 1 + right_pro and rand < 1 + right_pro + left_pro:
            [i1, j1] = Left(i1, j1)
        elif rand >= 1 + right_pro + left_pro and rand < 1 + right_pro + left_pro + up_pro:
            [i1, j1] = Up(i1, j1)
        else:
            [i1, j1] = Down(i1, j1)

#由于栈的特点，使得遍历时只能逆序遍历
print("路径为(显示为逆序)：",end='')
stack.Travel()