哈佛CS50python实现迷宫问题

递归求解的基本思路是，每个时刻总有一个当前位置，开始时这个位置是迷宫人口。如果当前位置就是出口，问题已解决。否则，如果从当前位置己无路可走，当前的探查失败，回退一步。取一个可行相邻位置用同样方式探查，如果从那里可以找到通往出口的路径，那么从当前位置到出口的路径也就找到了。

在回溯解法中，主要是用栈来存储可以探索的位置。利用栈后进先出的特点，在一条分路上探索失败时，回到最近一次存储的可探索位置。这是一种深度优先搜索的方法。

队列求解算法中，以队列存储可以探索的位置。利用队列先进先出的特点，实现在每个分支上同时进行搜索路径，直到找到出口。这是一种广度优先搜索的方法。一站式出国留学攻略 http://www.offercoming.com

下面的代码假定你的迷宫数据一定是合法的 （单一的入口和出口，不会打环，不会无解），如果数据不合法，可能导致死循环，数据合法性的检查你自己实现。

另外，我用 东南西北四个方向来代替所谓的上下左右，因为左右概念是相对的。 用python 2。

puzzle_walk 函数返回一个list, 每个元素是每次移动的路径坐标， 其第一个参数为迷宫的list数据， 第二个参数默认为 True 表示左手抹墙， False 则是右手抹墙。

简单说一下算法：首先找到入口格，设定初始面向 East ( 如果是右手抹墙则是 West），然后重复执行以下 *** 作：

 1. 如果当前格为最后一排且向南可以移动，则说明当前格为终点，结束。

 2. 根据当前格的数据，找到下一步需要面向的方向， 方法是，如果当前方向上有墙，则顺时针（右手抹墙则逆时针）转身，重复这一步骤直到面向的方向上可以行走. 这里可以参考 turn 函数

 3. 沿当前方向走一步， 参考 move 函数

 4. 逆时针（右手抹墙则顺时针）转身一次，使当前面对方向为第3步之后的左手（或右手）方向， 然后回到步骤1

最后， 我的代码假定迷宫入口一定是从第1行的North 方向进入，出口一定是从最后一行的 South 方向出去，如果要支持从第一行的其他方向进（比如从 (0, 0) 的West进） ，最后一行的其他方向出，你需修改查找入口的代码和判断出口的代码，这个很简单， 自己去搞定吧。

N = 0

E = 1

S = 2

W = 3

class Walker(object):

    def __init__(self, x, y, direction):

        # coordinates

        self.x = x

        self.y = y

        self.direction = direction

    def turn(self, clockwise=True):

        if clockwise:

            self.direction = (self.direction + 1) % 4

        else:

            self.direction = (self.direction + 4 - 1) % 4

    def move(self):

        if self.direction == N:

            self.x -= 1

        elif self.direction == E:

            self.y += 1

        elif self.direction == S:

            self.x += 1

        elif self.direction == W:

            self.y -= 1

    def get_coords(self):

        return (self.x, self.y)

    def get_direction(self):

        return self.direction

def puzzle_walk(puzzle, left_touching=True):

    route = []

    rows = len(puzzle)

    columns = len(puzzle[0])

    # locate the entrance

    coords = (-1, -1)

    for y in range(columns):

        cell = puzzle[0][y]

        if cell[N]:

            coords = (0, y)

            break

    assert coords[0] >= 0 and coords[1] >= 0

    walker = Walker(coords[0], coords[1], E if left_touching else W)

    while True:

        x, y = walker.get_coords()

        cell = puzzle[x][y]

        route.append(tuple([x, y]))

        if x == rows-1 and cell[S]:

            # found the exit

            break

        # turn to the direction where no wall blocks

        while not cell[walker.get_direction()]:

            walker.turn(left_touching)

        # move

        walker.move()

        # face to the direction of the hand

        walker.turn(not left_touching)

    return route

# 运行结果

>>> p=[[(False, True, True, False), (True, True, False, True), (False, False, True, True)], [(True, False, True, False), (False, True, False, False), (True, False, False, True)]]

# 左手抹墙

>>> puzzle_walk(p)

[(0, 1), (0, 2), (1, 2), (1, 1), (1, 2), (0, 2), (0, 1), (0, 0), (1, 0)]

# 右手抹墙

>>> puzzle_walk(p, False)

[(0, 1), (0, 0), (1, 0)]

# coding:UTF-8

global m,n,path,minpath,pathnum

m=7

n=7

k=  [0,1,2,3,4,5,6,7]  # 循环变量取值范围向量

a=[ [0,0,1,0,0,0,0,0],

[1,0,1,0,1,1,1,0],

[0,0,0,0,1,0,0,0],

[1,1,1,1,1,0,0,0],

[0,0,0,0,0,1,1,0],

[0,0,0,0,0,0,0,0],

[0,0,1,1,1,1,1,1],

[0,0,0,0,0,0,0,0]]  # 迷宫矩阵

b=[ [1,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0]]  # 状态矩阵

path=[]

minpath=[]

min=10000

step=0

pathnum=0

# print(a)

# print(b)

def nextone(x,y):

global path,minpath,m,n,min,step,pathnum

if (x==0)and(y==0):

path=[]

step=0

if (x==m)and(y==n):

pathnum+=1

print("step=",step)

print("path=",path)

if step<min:

min=step

minpath=path[:]

else:

if (x+1 in k)and(y in k):

if (b[x+1][y]==0)and(a[x+1][y]==0):

b[x+1][y]=1

path.append([x+1,y])

step+=1

nextone(x+1,y)

step-=1

path.remove([x+1,y])

b[x+1][y]=0  # 回溯

if (x in k)and(y+1 in k):

if (b[x][y+1]==0)and(a[x][y+1]==0):

b[x][y+1]=1

path.append([x,y+1])

step+=1

nextone(x,y+1)

step-=1

path.remove([x,y+1])

b[x][y+1]=0  # 回溯

if (x-1 in k)and(y in k):

if (b[x-1][y]==0)and(a[x-1][y]==0):

b[x-1][y]=1

path.append([x-1,y])

step+=1

nextone(x-1,y)

step-=1

path.remove([x-1,y])

b[x-1][y]=0  # 回溯

if (x in k)and(y-1 in k):

if (b[x][y-1]==0)and(a[x][y-1]==0):

b[x][y-1]=1

path.append([x,y-1])

step+=1

nextone(x,y-1)

step-=1

path.remove([x,y-1])

b[x][y-1]=0  # 回溯

nextone(0,0)

print()

print("min=",min)

print("minpath=",minpath)

print("pathnum=",pathnum)