迷宫问题

CodeWar

能不能走出去

题目：给一个如下形式的迷宫,‘.’为路，‘m’为障碍，起点为左上角终点为右下角，能走出返回True，反之为False

maze = "\n".join([
    ".....",
    "mmmm.",
    ".....",
    ".mmmm",
    "....."
])

初见：

#回溯法
#观赏
def mazeprint(maze):
    print("\n".join(["".join(i) for i in maze])+"\n")
#合法性判断
def valid(maze,x,y):
    if (x>=0 and x<len(maze)) and (y>=0 and y<len(maze[0])) and maze[x][y]==".":
        return True
    else:
        return False
#walk函数实现运动
def walk(maze,x=0,y=0):
    if x==len(maze)-1 and y==len(maze)-1:
        return True
    if valid(maze,x,y):
        print("start",x,y)
        mazeprint(maze)
        #o为走过的点
        maze[x][y]="o"
        mazeprint(maze)
        #右
        if walk(maze,x,y+1):
            return True
        #下
        elif walk(maze,x+1,y):
            return True
        #上
        elif walk(maze,x-1,y):
            return True
        #左
        elif walk(maze,x,y-1):
            return True
        else:
            #x为死路
            maze[x][y]="x"
            return False
    return False
def path_finder(maze):
    return(walk([list(iter(i)) for i in maze.split("\n")]))

亮点答案，同时也是最短路径：

#复平面坐标法
def path_finder(maze):
    g = maze.splitlines()
    end, bag = len(g[0]) -1 + len(g) * 1j - 1j, {0}
    grid = {x + y * 1j for y,l in enumerate(g) for x,c in enumerate(l) if '.' == c}
    #x+yj x:横坐标，y：纵坐标
    #end:终点
    #bag：走过的点
    #grid：可走的点
    while bag:
        if end in bag: return True
        grid -= bag
        #复数的幂实现四方向运动i^0=1,i^1=i,i^2=-1,i^3=-1
        #bag转为新的
        bag = grid & set.union(*({z + 1j ** k for k in range(4)} for z in bag))
    return False