全排列问题。
# box表示盒子
# book表示是否已被访问
box, book = [0]*10, [0]*10, n
# step表示站在第step个盒子面前
def dfs(step):
# 如果盒子数量大于n，则表示所有的n都放到和子里面了
if step==n+1:
print box
return
# 此时站在step个盒子面前，需要从n里面挑选出一个
# 没有被放入盒子的数放入盒子
for i in range(1, n):
# 找到没有放入盒子的数
if not book[i]:
# 放入盒子
book[i] = 1
box[step] = i
# 走到下一个盒子
dfs(step+1)
# 收回放入盒子的数，才能进行下一步尝试
book[i] = 0
return
n = 5
dfs(1)
迷宫问题。
# 表示下一步要走的位置
next_step = [[0,1],[1,0],[0,-1],[-1,0]]
# x,y 表示当前位置
# step 已经走了多少步
def dfs(x, y, step):
# 如果当前位置已经是目标位置
if x==p and y==q:
if step < min_step:
min_step = step
return
# 枚举4种走法
for k in range(len(next_step)):
# 计算下一个坐标
tx = x + next_step[k][0]
ty = y + next_step[k][1]
# 检查是否越界
if tx<1 or tx>n or ty<1 or ty>m:
continue
# 判断改点是否是障碍物或者已经在路径中
if a[tx][ty] == 0 and book[tx][ty] ==0:
book[tx][ty] = 1
dfs(tx, ty, step+1)
book[tx][ty] = 0
return
# 迷宫
a = [[]]
# 记录坐标
book = [[]]
# 迷宫的行和列
m,n = 0,0
# 终点坐标
p,q = 0,0
# 起点坐标
startx, starty = 0,0
# 初始化最小步数
min_step = float('inf')
book[startx, starty] = 1
dfs(startx, starty, 0)
print min_step
