迷宫程序Python

### 使用Python编写的迷宫生成与求解程序

#### 迷宫生成算法
一种常见的迷宫生成方法是基于深度优先搜索(DFS)，该算法通过随机选择墙壁并将其移除来创建通道，直到所有的单元格都连接在一起。下面是一个简单的实现例子：

import random

def make_maze(w = 16, h = 8):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def walk(x, y):
        vis[y][x] = 1

        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        random.shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "
            walk(xx, yy)

    walk(random.randrange(w), random.randrange(h))

    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s

print(make_maze())

这段代码定义了一个`make_maze()`函数用于构建指定宽度(`w`)和高度(`h`)的二维数组形式的迷宫[^1]。

#### 迷宫求解算法
对于迷宫求解来说，可以采用广度优先搜索(BFS)或者回溯法等策略。这里展示的是使用回溯法的一个实例:

def solve_maze(maze,start,end):
    directions=[(-1,0),(1,0),(0,-1),(0,1)] # 上 下 左 右四个方向
    
    rows=len(maze)-2
    cols=len(maze[0])-2

    path=[]

    def backtrack(row,col,path):
        if row<1 or col<1 or row>rows or col>cols or maze[row][col]=='#':
            return False
        
        pos=(row,col)
        
        if pos==end:
            path.append(pos)
            return True
            
        maze[row][col]='#' # 标记当前位置已经走过
        path.append(pos)

        found=False
        for dr,dc in directions:
            newr,newc=row+dr,col+dc
            if not found and backtrack(newr,newc,path[:]):
                found=True
                
        if not found:path.pop()
        return found

    solution_path=[]
    success=backtrack(start[0],start[1],solution_path)
    
    if success:return solution_path
    else:return None

maze=[
"+--+",
"|  |",
"|  |",
"|  |",
"+--+"
]

start=(1,1); end=(3,3)
result=solve_maze(maze,start,end)
if result is not None:
    print("Path Found:",result)
else:
    print("No Path Exists.")

此段脚本实现了`solve_maze()`函数接收一个由字符组成的列表作为参数代表迷宫地图，并尝试找到从起点到终点的一条合法路径[^4]。