Shortest path 迷宫寻路

收藏到CSDN网摘


走迷宫是acm经常出现的一类问题,有多重方法可以解决,例如A*,广度优先搜索,深度优先搜索等.广度优先搜素可以保证一旦找到路径,必定为最短路径.
广度优先搜索的实例如下(在12*12的迷宫中从(1,1)走到(10,10),边界是围墙,0为可通过,1为不可通过):

class Node(object):
    # x,y,parent node
    def __init__(self,x,y,p=None):
        self.x = x
        self.y = y
        self.p = p

    # check movement from self to n
    def decode(self,n):
        md = {(1,0):'S',
              (-1,0):'N',
              (0,1):'E',
              (0,-1):'W'}
        return md[(self.y-n.y,self.x-n.x)]

    # str()
    def __repr__(self):
        return '(%s,%s)' % (str(self.y),str(self.x))
        
def checkio(data):
    # find the path with breadth first search
    visited = [[0]*12 for i in range(12)]   # visited position
    path = [Node(1,1)]      # path position
    visited[1][1] = 1       # start position
    # success flag
    flag = 0
    cv = Node(0,0)        # used for retrieve path
    # start loop
    while len(path)>0:
        cv = path.pop(0)    # first node
        x,y = cv.x,cv.y     # col, row
        visited[y][x] = 1   # mark visited
        if x==10 and y==10: # reach the outlet
            flag = 1
            break
        # right
        if x<10 and data[y][x+1]==0 and visited[y][x+1]!=1:
            path.append(Node(x+1,y,cv))
        # down
        if y<10 and data[y+1][x]==0 and visited[y+1][x]!=1:
            path.append(Node(x,y+1,cv))
        # left
        if x>1 and data[y][x-1]==0 and visited[y][x-1]!=1:
            path.append(Node(x-1,y,cv))
        # up
        if y>1 and data[y-1][x]==0 and visited[y-1][x]!=1:
            path.append(Node(x,y-1,cv))
    if flag:
        cc = cv     # current node
        nc = cv.p   # parent node
        s = ''      # path move
        ps = []     # path position
        while nc:   # decode path
            ps.append(cc)
            s += cc.decode(nc)
            cc = nc
            nc = nc.p
        ps.append((1,1))
        # output path
##        print ps[::-1]
        # output decoded path move
        return s[::-1]
    else:
        return 'No path'

#This code using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))
    #be carefull with infinity loop
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        ]))