下面的代码假定你的迷宫数据一定是合法的 （单一的入口和出口，不会打环，不会无解），如果数据不合法，可能导致死循环，数据合法性的检查你自己实现。
另外，我用 东南西北四个方向来代替所谓的上下左右，因为左右概念是相对的。 用python 2。
puzzle_walk 函数返回一个list, 每个元素是每次移动的路径坐标， 其第一个参数为迷宫的list数据， 第二个参数默认为 True 表示左手抹墙， False 则是右手抹墙。
简单说一下算法：首先找到入口格，设定初始面向 East ( 如果是右手抹墙则是 West），然后重复执行以下操作：
1. 如果当前格为最后一排且向南可以移动，则说明当前格为终点，结束。
2. 根据当前格的数据，找到下一步需要面向的方向， 方法是，如果当前方向上有墙，则顺时针（右手抹墙则逆时针）转身，重复这一步骤直到面向的方向上可以行走. 这里可以参考 turn 函数
3. 沿当前方向走一步， 参考 move 函数
4. 逆时针（右手抹墙则顺时针）转身一次，使当前面对方向为第3步之后的左手（或右手）方向， 然后回到步骤1
最后， 我的代码假定迷宫入口一定是从第1行的North 方向进入，出口一定是从最后一行的 South 方向出去，如果要支持从第一行的其他方向进（比如从 (0, 0) 的West进） ，最后一行的其他方向出，你需修改查找入口的代码和判断出口的代码，这个很简单， 自己去搞定吧。
N = 0
E = 1
S = 2
W = 3
class Walker(object):
def __init__(self, x, y, direction):
# coordinates
self.x = x
self.y = y
self.direction = direction
def turn(self, clockwise=True):
if clockwise:
self.direction = (self.direction + 1) % 4
else:
self.direction = (self.direction + 4 - 1) % 4
def move(self):
if self.direction == N:
self.x -= 1
elif self.direction == E:
self.y += 1
elif self.direction == S:
self.x += 1
elif self.direction == W:
self.y -= 1
def get_coords(self):
return (self.x, self.y)
def get_direction(self):
return self.direction
def puzzle_walk(puzzle, left_touching=True):
route = []
rows = len(puzzle)
columns = len(puzzle[0])
# locate the entrance
coords = (-1, -1)
for y in range(columns):
cell = puzzle[0][y]
if cell[N]:
coords = (0, y)
break
assert coords[0] >= 0 and coords[1] >= 0
walker = Walker(coords[0], coords[1], E if left_touching else W)
while True:
x, y = walker.get_coords()
cell = puzzle[x][y]
route.append(tuple([x, y]))
if x == rows-1 and cell[S]:
# found the exit
break
# turn to the direction where no wall blocks
while not cell[walker.get_direction()]:
walker.turn(left_touching)
# move
walker.move()
# face to the direction of the hand
walker.turn(not left_touching)
return route
# 运行结果
>>> p=[[(False, True, True, False), (True, True, False, True), (False, False, True, True)], [(True, False, True, False), (False, True, False, False), (True, False, False, True)]]
# 左手抹墙
>>> puzzle_walk(p)
[(0, 1), (0, 2), (1, 2), (1, 1), (1, 2), (0, 2), (0, 1), (0, 0), (1, 0)]
# 右手抹墙
>>> puzzle_walk(p, False)
[(0, 1), (0, 0), (1, 0)]
示例：# coding:UTF-8
global m,n,path,minpath,pathnum
m=7
n=7
k= [0,1,2,3,4,5,6,7] # 循环变量取值范围向量
a=[ [0,0,1,0,0,0,0,0],
[1,0,1,0,1,1,1,0],
[0,0,0,0,1,0,0,0],
[1,1,1,1,1,0,0,0],
[0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0]] # 迷宫矩阵
b=[ [1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]] # 状态矩阵
path=[]
minpath=[]
min=10000
step=0
pathnum=0
# print(a)
# print(b)
def nextone(x,y):
global path,minpath,m,n,min,step,pathnum
if (x==0)and(y==0):
path=[]
step=0
if (x==m)and(y==n):
pathnum+=1
print("step=",step)
print("path=",path)
if step<min:
min=step
minpath=path[:]
else:
if (x+1 in k)and(y in k):
if (b[x+1][y]==0)and(a[x+1][y]==0):
b[x+1][y]=1
path.append([x+1,y])
step+=1
nextone(x+1,y)
step-=1
path.remove([x+1,y])
b[x+1][y]=0 # 回溯
if (x in k)and(y+1 in k):
if (b[x][y+1]==0)and(a[x][y+1]==0):
b[x][y+1]=1
path.append([x,y+1])
step+=1
nextone(x,y+1)
step-=1
path.remove([x,y+1])
b[x][y+1]=0 # 回溯
if (x-1 in k)and(y in k):
if (b[x-1][y]==0)and(a[x-1][y]==0):
b[x-1][y]=1
path.append([x-1,y])
step+=1
nextone(x-1,y)
step-=1
path.remove([x-1,y])
b[x-1][y]=0 # 回溯
if (x in k)and(y-1 in k):
if (b[x][y-1]==0)and(a[x][y-1]==0):
b[x][y-1]=1
path.append([x,y-1])
step+=1
nextone(x,y-1)
step-=1
path.remove([x,y-1])
b[x][y-1]=0 # 回溯
nextone(0,0)
print()
print("min=",min)
print("minpath=",minpath)
print("pathnum=",pathnum)
