算法学习之【回溯法】--迷宫问题
2021-06-23 12:07
标签：元素 return 表示 == 代码 sub 递归 不能 spl 定义一个二维数组N*M（其中2
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0]，即第一空格是可以走的路。 Input 一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 Output 左上角到右下角的最短路径，格式如样例所示。 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 元素--状态空间分析：每个坐标是是一个元素，每次可以在上一个坐标基础上向右[0,1]或者向下[1,0]移动一步。所以这里可以看出，元素是不固定的，状态空间固定。 算法学习之【回溯法】--迷宫问题 标签：元素 return 表示 == 代码 sub 递归 不能 spl 原文地址：https://www.cnblogs.com/zx3212/p/9674014.html题目描述
分析
代码
while True:
try:
n = list(map(int,input().split())) # 输入一个N*M的数组
N = n[0]
M = n[1]
m = []
x,y = 0,0
result = [[x,y]] # 定义其实位置0，0
for i in range(N): # 依次输入二维数组，组成一个N*m的数组
m.append(list(map(int,input().split())))
# 冲突检测，如果下一步是1 ，表示为墙，冲突了
def conflict(i):
if m[i[0]][i[1]] == 1:
return True
return False # 无冲突
# 回溯法（递归版）
def foo():
global x, y, result
if x == N-1 and y == M-1: # 判断是否到终点
for i in result:
print(‘({},{})‘.format(i[0],i[1]))
else:
for j in [[0,1],[1,0]]: # 元素空间为[0,1],[1,0]
# 向对应方向挪动一步
x += j[0]
y += j[1]
if x > N-1 or y > M-1: # 如果超出边界，回退
x -= j[0]
y -= j[1]
continue
s = [x,y]
result.append(s) # 加入这个坐标
if not conflict(s):
foo() # 如果不冲突，继续下一步
result.pop() #如果冲突，删除刚才加入的这个坐标点，并执行下面两步回退
x -= j[0]
y -= j[1]
foo()
except:
break