作品 5 数字迷宫游戏
1.1 项目简介
数字迷宫是又 0,1 组成的一个 m 行 n 列的二维矩阵,例如:
0 0 0 1
0 0 0 0
0 0 1 0
就是一个 3 行 4 列的迷宫,其中每个元素是 0 或者 1,一个小虫从左上角的(0,0)入口,只能向上下左
右行走,而且只能到达元素值为 0 的点,值为 1 的点不可以到达,然后从右下角的(2,3)点走出来,程序的
功能就是为这个小虫找到所有的不重复的道路。例如这个迷宫的道路一共有下列 5 条:
Path 1 :->(0,0)->(0,1)->(0,2)->(1,2)->(1,3)->(2,3)
Path 2 :->(0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)
Path 3 :->(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)
Path 4 :->(0,0)->(1,0)->(1,1)->(0,1)->(0,2)->(1,2)->(1,3)->(2,3)
Path 5 :->(0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(1,2)->(1,3)->(2,3)
Path 6 :->(0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(0,1)->(0,2)->(1,2)->(1,3)->(2,3)
1.2 迷宫道路深度优先算法
先构造一个节点的类 NodeClass 如下:
class NodeClass:
def __init__(self,i,j,v):
self.i=i
self.j=j
self.v=v
其中(i,j)是一个节点位置,v=0,1,2,3 是上下左右四个反向的走向。
构造一个栈 stack,它的每个元素是一个 NodeClass 的对象,存储小虫走过的道路,算法如下:
(1) 把点(0,0,0)入栈,top=0;
(2) 如果栈不空,那么考虑栈顶的节点得到 v=stack[top].v,然后让 stack[top].v 增加 1 以便下次朝着另
外一个方向前进。
(3) 根据 v=0,1,2,3 确定新的位置(i,j)如下:
if v==0:
i=node.i
j=node.j-1
elif v==1:
i=node.i
j=node.j+1
elif v==2:
i=node.i-1
j=node.j
elif v==3:
i=node.i+1
j=node.j
如果(i,j)是可以到达的合理位置,而且目前道路上没有到过这个位置,那么就让这个节点入栈:
if v<4: