method1 递归求解
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
def mark(maze, pos):
maze[pos[0]][pos[1]] = 2
def passable(maze, pos):
return maze[pos[0]][pos[1]] == 0
def find_path(maze, pos, end):
mark(maze, pos)
if pos == end:
print(pos, end=" ")
return True
for i in range(4):
nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
if passable(maze, nextp):
if find_path(maze, nextp, end):
print(pos, end=" ")
return True
return False
maze = [[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1],
[1,0,0,0,1, 1,0,0,0,1, 0,0,0,1],
[1,0,1,0,0, 0,0,1,0,1, 0,1,0,1],
[1,0,1,0,1, 1,1,1,0,1, 0,1,0,1],
[1,0,1,0,0, 0,0,0,0,1, 1,1,0,1],
[1,0,1,1,1, 1,1,1,1,1, 0,0,0,1],
[1,0,1,0,0, 0,0,0,0,0, 0,1,0,1],
[1,0,0,0,1, 1,1,0,1,0, 1,1,0,1],
[1,0,1,0,1, 0,1,0,1,0, 1,0,0,1],
[1,0,1,0,1, 0,1,0,1,1, 1,1,0,1],
[1,0,1,0,0, 0,1,0,0,1, 0,0,0,1],
[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1]]
pos = (1,1)
end = (10,12)
find_path(maze, pos, end)
(10, 12) (9, 12) (8, 12) (7, 12) (6, 12) (5, 12) (5, 11) (5, 10) (6, 10) (6, 9) (6, 8) (6, 7) (6, 6) (6, 5) (6, 4) (6, 3) (7, 3) (7, 2) (7, 1) (6, 1) (5, 1) (4, 1) (3, 1) (2, 1) (1, 1)
True
method2 队列法
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
def mark(maze, pos):
maze[pos[0]][pos[1]] = 2
def passable(maze, pos):
return maze[pos[0]][pos[1]] == 0
def maze_solver_queue(maze, start, end):
if start == end:
print(start)
return
qu = SQueue()
mark(maze, start)
qu.enqueue(start)
while not qu.is_empty():
pos = qu.dequeue()
for i in range(4):
nextp = (pos[0] + dirs[i][0],
pos[1] + dirs[i][1])
if passable(maze, nextp):
if nextp == end:
print("Path find.")
return
mark(maze, nextp)
qu.enqueue(nextp)
print("No path.")
maze = [[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1],
[1,0,0,0,1, 1,0,0,0,1, 0,0,0,1],
[1,0,1,0,0, 0,0,1,0,1, 0,1,0,1],
[1,0,1,0,1, 1,1,1,0,1, 0,1,0,1],
[1,0,1,0,0, 0,0,0,0,1, 1,1,0,1],
[1,0,1,1,1, 1,1,1,1,1, 0,0,0,1],
[1,0,1,0,0, 0,0,0,0,0, 0,1,0,1],
[1,0,0,0,1, 1,1,0,1,0, 1,1,0,1],
[1,0,1,0,1, 0,1,0,1,0, 1,0,0,1],
[1,0,1,0,1, 0,1,0,1,1, 1,1,0,1],
[1,0,1,0,0, 0,1,0,0,1, 0,0,0,1],
[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1]]
pos = (1,1)
end = (10,12)
maze_solver_queue(maze, pos, end)
Path find.
method3 栈和回溯法 有错误
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
def mark(maze, pos):
maze[pos[0]][pos[1]] = 2
def passable(maze, pos):
return maze[pos[0]][pos[1]] == 0
def maze_solver(maze, start, end):
if start == end:
print(start)
return
st = SStack()
mark(maze, start)
st.push((start, 0))
while not st.is_empty():
pos, nxt = st.pop()
for i in range(nxt, 4):
nextp = (pos[0] + dirs[i][0],
pos[1] + dirs[i][1])
if nextp == end:
while not st.is_empty:
print(st.pop(), end=" ")
return
if passable(maze, nextp):
st.push((pos, i+1))
mark(maze, nextp)
st.push((nextp, 0))
break
print("No path found...")
maze = [[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1],
[1,0,0,0,1, 1,0,0,0,1, 0,0,0,1],
[1,0,1,0,0, 0,0,1,0,1, 0,1,0,1],
[1,0,1,0,1, 1,1,1,0,1, 0,1,0,1],
[1,0,1,0,0, 0,0,0,0,1, 1,1,0,1],
[1,0,1,1,1, 1,1,1,1,1, 0,0,0,1],
[1,0,1,0,0, 0,0,0,0,0, 0,1,0,1],
[1,0,0,0,1, 1,1,0,1,0, 1,1,0,1],
[1,0,1,0,1, 0,1,0,1,0, 1,0,0,1],
[1,0,1,0,1, 0,1,0,1,1, 1,1,0,1],
[1,0,1,0,0, 0,1,0,0,1, 0,0,0,1],
[1,1,1,1,1, 1,1,1,1,1, 1,1,1,1]]
pos = (1,1)
end = (10,12)
maze_solver(maze, pos, end)
