迷宫问题

Bella666

迷宫问题，PYTHON 小学生不会写，求大佬帮忙。要用python写。

RIXO

呃，是这个迷宫路径的问题吗？
https://fishc.com.cn/thread-122768-1-1.html

Bella666

RIXO 发表于 2018-9-25 14:26
呃，是这个迷宫路径的问题吗？
https://fishc.com.cn/thread-122768-1-1.html

不是，

                               
登录/注册后可看大图

第一问，这个迷宫又几个门
第二问，这个迷宫有多少个连在一块的墙
第三问，有几个不可以进入的区域
第四问，有几个可以进入的区域
第五问，有几个死胡同
第六问，有几个没有交叉，没有死胡同的通路

Bella666

求助

RIXO

Bella666 发表于 2018-9-25 19:32
求助

英文文档看的我一脸懵逼，这谁出的题，太缺德了
呃，因为没学过算法，可能有点问题，按我的思路来讲
就是一个点，有四个方向，上下左右可以移动，点 = 0 四个方向都能移，点 = 1 不能移动上，点 = 2 不能移动右，点 = 3 不能移动上 左 。
呃，这样一来就等于扩展矩阵，矩阵的数量乘四倍
1 = 1  1       2   =  0   1       3    =   1    1   
      0  0                0   1                  1    0
移动方向  mov（x,y） =   左（1，0）上（0，1）右（-1，0）下（0，-1）
找路的话需要先遍历四个边，边有没有0存在，然后逐个计算有没有出路
这个应该是题目里面的门，关于不可进入区域，和可以进入区域，还不清楚是啥
死胡同就是走不通的路径，按照帖子里面的求解可以求出来
通路也能算出来
如此一考虑，这已经是200行代码以上才能做的事情
构建扩展出来的那个矩阵还没想好怎么实现。。。。。
这题难度太大了，放弃吧

Bella666

RIXO 发表于 2018-9-25 20:28
英文文档看的我一脸懵逼，这谁出的题，太缺德了
呃，因为没学过算法，可能有点问题，按我的思 ...

可进入区域就是有入口，不可进入区域就是周围全是墙。
谢谢，大佬解答

RIXO

要叫这位大佬来解@冬雪雪冬

colinshi

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,1,0,1],
[1,1,1,1,1,1,1,1,1,1]
]

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x, y - 1),
    ]
from collections import deque
def maze_find(x1, y1, x2, y2):
    stack = deque()
    stack.append((x1, y1))
    while len(stack) > 0:
        curNode = stack[-1]
        if curNode[0] == x2 and curNode[1] == y2:
            for p in stack:
                print(p)
            return True
        for i in dirs:
            nextNode = i(*curNode)
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = -1
                break
        else:
            maze[curNode[0]][curNode[1]] = -1
            stack.pop()
    print('没有找到出口')
    return False

#maze_find(1, 1, 8, 8)

def r_path(path):
    curNode = path.pop()
    rpath = []
    while curNode[2] != -1:
        rpath.append((curNode[0:2]))
        curNode = path[curNode[2]]
    return reversed(rpath)

def maze_q(x1, y1, x2, y2):
    stack = deque()#建立一个队列
    stack.append((x1, y1, -1))#初始化第一个起点
    rpath = [] #结果路径
    while len(stack) > 0: #当有队列存在循环
        curNode = stack.popleft()#当前队列的第一个位置为当前位置
        rpath.append(curNode)
        for i in dirs:
            nextNode = i(curNode[0], curNode[1])
            #print(nextNode)
            if nextNode[0] == x2 and nextNode[1] == y2:
                print('开始走迷宫：')
                print('起点位置:', (x1, y1))
                for i in r_path(rpath):
                    print('途径位置:', i)
                print('终点位置:', (x2, y2))
                return True
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append((nextNode[0], nextNode[1], len(rpath)-1))
                maze[nextNode[0]][nextNode[1]] = -1
    print('没有找到出口')
    return False
maze_q(1, 1, 8, 8)

给你看一下我之前写的迷宫代码，基本上的思路就是先确定可以走的方向上下左右，然后每次走玩判断是不是到达终点，并记录该点已经走过。因为题目是全英文的，实在是看的头大。。。所以发一下自己之前写的吧

Bella666

colinshi 发表于 2018-9-26 14:56
给你看一下我之前写的迷宫代码，基本上的思路就是先确定可以走的方向上下左右，然后每次走玩判断是不是到 ...

谢谢你！