迷宫问题

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

1. maze = [
   
2. [1,1,1,1,1,1,1,1,1,1],
   
3. [1,0,0,1,0,0,0,1,0,1],
   
4. [1,0,0,1,0,0,0,1,0,1],
   
5. [1,0,0,0,0,1,1,0,0,1],
   
6. [1,0,1,1,1,0,0,0,0,1],
   
7. [1,0,0,0,1,0,0,0,0,1],
   
8. [1,0,1,0,0,0,1,0,0,1],
   
9. [1,0,1,1,1,0,1,1,0,1],
   
10. [1,1,0,0,0,0,0,1,0,1],
    
11. [1,1,1,1,1,1,1,1,1,1]
    
12. ]
    
13. 
    
14. dirs = [
    
15.     lambda x, y: (x + 1, y),
    
16.     lambda x, y: (x - 1, y),
    
17.     lambda x, y: (x, y + 1),
    
18.     lambda x, y: (x, y - 1),
    
19.     ]
    
20. from collections import deque
    
21. def maze_find(x1, y1, x2, y2):
    
22.     stack = deque()
    
23.     stack.append((x1, y1))
    
24.     while len(stack) > 0:
    
25.         curNode = stack[-1]
    
26.         if curNode[0] == x2 and curNode[1] == y2:
    
27.             for p in stack:
    
28.                 print(p)
    
29.             return True
    
30.         for i in dirs:
    
31.             nextNode = i(*curNode)
    
32.             if maze[nextNode[0]][nextNode[1]] == 0:
    
33.                 stack.append(nextNode)
    
34.                 maze[nextNode[0]][nextNode[1]] = -1
    
35.                 break
    
36.         else:
    
37.             maze[curNode[0]][curNode[1]] = -1
    
38.             stack.pop()
    
39.     print('没有找到出口')
    
40.     return False
    
41. 
    
42. #maze_find(1, 1, 8, 8)
    
43. 
    
44. def r_path(path):
    
45.     curNode = path.pop()
    
46.     rpath = []
    
47.     while curNode[2] != -1:
    
48.         rpath.append((curNode[0:2]))
    
49.         curNode = path[curNode[2]]
    
50.     return reversed(rpath)
    
51. 
    
52. def maze_q(x1, y1, x2, y2):
    
53.     stack = deque()#建立一个队列
    
54.     stack.append((x1, y1, -1))#初始化第一个起点
    
55.     rpath = [] #结果路径
    
56.     while len(stack) > 0: #当有队列存在循环
    
57.         curNode = stack.popleft()#当前队列的第一个位置为当前位置
    
58.         rpath.append(curNode)
    
59.         for i in dirs:
    
60.             nextNode = i(curNode[0], curNode[1])
    
61.             #print(nextNode)
    
62.             if nextNode[0] == x2 and nextNode[1] == y2:
    
63.                 print('开始走迷宫：')
    
64.                 print('起点位置:', (x1, y1))
    
65.                 for i in r_path(rpath):
    
66.                     print('途径位置:', i)
    
67.                 print('终点位置:', (x2, y2))
    
68.                 return True
    
69.             if maze[nextNode[0]][nextNode[1]] == 0:
    
70.                 stack.append((nextNode[0], nextNode[1], len(rpath)-1))
    
71.                 maze[nextNode[0]][nextNode[1]] = -1
    
72.     print('没有找到出口')
    
73.     return False
    
74. maze_q(1, 1, 8, 8)

复制代码

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

Bella666

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

谢谢你！