迷宫问题

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)