迷宫

作者: 你好宝宝 | 来源:发表于2020-03-15 12:43 被阅读0次

题目描述:

输入一个二维数组,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
【输入】
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。

【输出】
左上角到右下角的最短路径,格式如样例所示。

【输入样例】
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路

广度优先遍历:用一个列表记录广度优先遍历的节点,每个节点设置一个前向索引记录该节点的父亲节点的位置

import numpy as np
class node:
    def __init__(self, x, y, pre):
        self.x = x
        self.y = y
        self.pre = pre


if __name__ == "__main__":
    puzzle = [
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
    ]
    visit = np.zeros(20).reshape(4, 5)
    pre = 0
    tail = 0
    queue = [node(0, 0, -1)]
    visit[0][0]=1
    tail += 1
    flag = 0

    move = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    while(pre < tail):
        cur = queue[pre]

        for i in range(len(move)):  # 移动
            next_x = cur.x+move[i][0]
            next_y = cur.y+move[i][1]

            if next_x not in range(len(puzzle)) or next_y not in range(len(puzzle[0])):  # 超出边界
                continue

            if not visit[next_x][next_y] and puzzle[next_x][next_y]==0:  # 如果没有访问过且不为0
                visit[next_x][next_y] = 1
                queue.append(node(next_x, next_y, pre))
                tail += 1

            if next_x == len(puzzle)-1 and next_y == len(puzzle[0])-1:  # 如果访问到尾节点,则终止
                flag = 1
                break

        pre += 1

    if flag == 1:
        trace=[]
        cur = queue[-1]
        pre = cur.pre
        while pre != -1:
            trace.append((cur.x,cur.y))
            cur = queue[pre]
            pre = cur.pre
        trace.append((0,0))

        for item in trace[::-1]:
            print(item)
      

当仅仅是求通路不要求最短也可以使用深度优先:一直按同一个方向进行遍历,当遇到不能继续访问的节点时进行回溯

import numpy as np


class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.dir = 1

    def get_dir(self):
        return self.dir

    def change_dir(self):
        self.dir += 1

    

def dfs(puzzle,end_x,end_y):
    start_x = 0
    start_y = 0
    stack = [Node(start_x, start_y)]

    while(stack):
        node = stack[-1]
        direction = node.get_dir()
        x = node.x
        y = node.y

        puzzle[x][y] = 1 #避免重复访问该节点
        if x == end_x and y == end_y:
            return stack

        if direction == 1:
            if x+1 in range(len(puzzle)) and puzzle[x+1][y] == 0: #判断是否越界,以及是否可以经过
                stack.append(Node(x+1, y))
            node.change_dir() # 切换至下一个方向继续运行
            continue
        elif direction == 2:
            if x-1 in range(len(puzzle)) and puzzle[x-1][y] == 0:
                stack.append(Node(x-1, y))
            node.change_dir()
            continue
        elif direction == 3:
            if y+1 in range(len(puzzle[0])) and puzzle[x][y+1] == 0:
                stack.append(Node(x, y+1))
            node.change_dir()
            continue
        elif direction == 4:
            if y-1 in range(len(puzzle[0])) and puzzle[x][y-1] == 0:
                stack.append(Node(x, y-1))
            node.change_dir()
            continue

        node=stack.pop() # 当direction大于等于4证明路径不可达
        puzzle[node.x][node.y]=0 # 当前路径已经不包含该节点,解除该节点的不可访问锁,这样当回溯到这个节点时可以继续访问该节点的另一个方向

    return None


if __name__ == "__main__":
    puzzle = [
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
    ]
    stack = dfs(puzzle, len(puzzle)-1, len(puzzle[0])-1)
    for node in stack:
        print((node.x,node.y))

相关文章

  • 《相似的迷宫》

    相似的迷宫 不要仅仅是一棵行走的树 在人的迷宫 在树的迷宫 在我的迷宫 在生命的迷宫 在物的迷宫 在时间的迷宫 在...

  • 帮派迷宫 - 迷宫补贴

    【帮派迷宫攻略】 名词定义 迷宫之主:迷宫的发起者,付费开启迷宫的玩家化蛇:帮主开的,大家抢,非帮主开的由迷宫之主...

  • 我喜欢的一本书

    我最喜欢的书是熊出没大迷宫,因为我觉得迷宫书特别的好玩,里面有正方的迷宫 还有云彩的迷宫等各种各样的迷宫,种类特别...

  • 2019-03-16

    乐高积木搭迷宫 孩子爸用乐高搭了基础小迷宫,晶晶没有把注意力放在怎么走迷宫上,而是摆放迷宫玩具上。跳跃走迷宫,没有...

  • 画迷宫

    今天,我在美术课上,老师给我们拿了一个迷宫兔子和几本迷宫书,我们看完迷宫书,老师说:“今天的主题是画迷宫”...

  • 基于Java的迷宫老鼠游戏

    一、功能简介 迷宫老鼠系统包括以下功能: 自定义迷宫大小 使用图的深度遍历随机生成迷宫 用户使用鼠标绘制自定义迷宫...

  • 如何成为更优秀的数据专家?(一)

    数据工作就像个迷宫,而这个迷宫没有“大师速成班”,没有让人一蹴而就直接穿越整个迷宫的道路。 通过这个迷宫,需要通过...

  • 不是迷宫的迷宫

    戴着牛头面具的小孩, 行走在自己建立的迷宫, 地图在他的手中, 他能出去却不想出去。 他一直在这里等待, 你问我他...

  • wind爸爸:5分钟设计迷宫游戏

    今天我们开始聊如何和孩子一起自己设计更好玩的迷宫游戏。 自己设计迷宫游戏我把它分为纸上迷宫、DIY迷宫两大类,下面...

  • 宗教总是超脱的

    也许每个人出生时都处于迷宫之中。 真正能走出迷宫的,是哪些跳出迷宫看迷宫的人。 不识庐山真面目,只缘自在此山中。有...

网友评论

      本文标题:迷宫

      本文链接:https://www.haomeiwen.com/subject/wouhehtx.html