# 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)
您问的是Python求解迷宫问题吧。有三种求解方法，递归求解、回溯求解和队列求解。
递归求解的基本思路是，每个时刻总有一个当前位置，开始时这个位置是迷宫人口。如果当前位置就是出口，问题已解决。否则，如果从当前位置己无路可走，当前的探查失败，回退一步。取一个可行相邻位置用同样方式探查，如果从那里可以找到通往出口的路径，那么从当前位置到出口的路径也就找到了。
在回溯解法中，主要是用栈来存储可以探索的位置。利用栈后进先出的特点，在一条分路上探索失败时，回到最近一次存储的可探索位置。这是一种深度优先搜索的方法。
队列求解算法中，以队列存储可以探索的位置。利用队列先进先出的特点，实现在每个分支上同时进行搜索路径，直到找到出口。这是一种广度优先搜索的方法。一站式出国留学攻略 http://www.offercoming.com
