Python BFS 迷宫问题

妖狐艹你老母 2023-07-24 03:06 4阅读 0赞

import queue
    print("Please input the size of the square:")
    n = int(input())
    map_ = [([0]*n) for i in range(n)] #创建地图
    vis = [([0]*n) for i in range(n)] #访问标记
    front = [([0]*n) for i in range(n)] #路径
    s,t = [0,0],[n-1,n-1] #初始化猫(s)鼠(t)位置
    xPos = [1,0,-1,0] # x坐标方向
    yPos = [0,1,0,-1] # y坐标方向
    
    
    def bfs(x,y):
        q = queue.Queue()
        q.put([x,y])
        vis[x][y]=1
        while q.qsize() != 0:
            now = q.get()
            if now == [n-1,n-1]:
                return
            for i in range(0,4):
                xx = now[0] + xPos[i]
                yy = now[1] + yPos[i]
                if xx<0 or xx>n-1 or yy<0 or yy>n-1:
                    continue
                elif map_[xx][yy] == 1 or vis[xx][yy]==1:
                    continue
                else:
                    q.put([xx,yy])
                    vis[xx][yy]=1
                    front[xx][yy]=now # 记录上一次的位置
        return
    
    def printRoad():
        q = queue.LifoQueue() #栈
        now=[n-1,n-1]
        while now != [0,0]:
            # print(now)
            q.put(now)
            now = front[now[0]][now[1]]
        print("The road：")
        while q.qsize():
            temp = q.get()
            print(temp)
    
    for i in range(n):
        map_[i] = input().split(" ")
    
    map_[0][0]='S' #标记猫位置
    map_[n-1][n-1]='T' #标记鼠位置
    # print(vis)
    # print(map_[1][0])
    # print(vis[1][0])
    
    bfs(0,0)
    printRoad()
    
    # 输入
    # S 代表起点（猫的位置）T代表终点（鼠的位置）
    # 1 代表有路障， 0代表没有
    ''' input: 6 S 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 T '''

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关走迷宫(BFS)

走迷宫给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1

叁歲伎倆/ 2024年03月30日 11:09/ 0 赞/ 49 阅读

相关 POJ3984 迷宫问题（BFS）

\include<cstdio> \include<cstring> \include<queue> \include<vector> using namesp

爱被打了一巴掌/ 2024年02月17日 18:25/ 0 赞/ 8 阅读

相关 Python BFS 迷宫问题

import queue print("Please input the size of the square:") n = int(input())

妖狐艹你老母/ 2023年07月24日 03:06/ 0 赞/ 5 阅读

相关广度优先搜索BFS（迷宫问题）

问题及代码：给出迷宫的图纸和初始终点位置，用DFS求最小步数。 include <iostream> include <cstring>

逃离我推掉我的手/ 2022年07月28日 04:11/ 0 赞/ 215 阅读

相关迷宫问题 DFS写法 BFS写法

定义一个二维数组： int maze\[5\]\[5\] = \{ 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0

红太狼/ 2022年06月18日 09:56/ 0 赞/ 213 阅读

相关 BFS求解迷宫问题

以前学习C的时候，老师布置过一个拓展作业，实现迷宫的求解，当时没有学习数据结构，有点难以下手，现在学完数据结构已经将近2年，终于解决了这个问题。给定一个n\m大小的迷

女爷i/ 2022年05月20日 06:37/ 0 赞/ 251 阅读

相关迷宫问题(bfs)

定义一个二维数组： int maze\[5\]\[5\] = \{ 0, 1, 0, 0, 0, 0, 1, 0, 1, 0,

忘是亡心i/ 2022年05月15日 01:16/ 0 赞/ 248 阅读

相关 POJ 3984 迷宫问题 —————— BFS

Language:Default 迷宫问题 <table> <tbody> <tr> <td><b>Time Limit:</b> 1000MS</td>

- 日理万妓/ 2022年05月12日 02:34/ 0 赞/ 217 阅读

相关 POJ 3984 迷宫问题（bfs）

嗯... 题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 这道

深藏阁楼爱情的钟/ 2021年10月29日 21:12/ 0 赞/ 371 阅读

相关 BFS之迷宫问题-输出路径

迷宫问题引言例题一(打印坐标) 例题二(打印方向) 引言广度优先搜索（BFS）可以很方便的去解决迷宫问

灰太狼/ 2021年09月21日 08:54/ 0 赞/ 329 阅读