find shorttest path

た入场券 2022-03-15 19:04 128阅读 0赞

def find_shortest_path(maze):
        '''
        maze = [['X', 'X', 'O', 'S', 'X'],
                  ['X', 'X', 'O', 'O', 'X'],
                  ['X', 'X', 'O', 'X', 'X'],
                  ['X', 'X', 'O', 'E', 'X']]'''
        a=[]
        b=[]
        s1=s2=e1=e2=0
        for i in range(len(maze)):
            for j in range(len(maze[0])):
                if maze[i][j]=='S':
                    s1=i
                    s2=j
                if maze[i][j]=='E':
                    e1=i
                    e2=j
        a.append([(s1,s2),])
        while len(a)>0:
            b=[]
            for aaa in a:
                #up
                aa=aaa[:]
                if aa[-1][0]-1>=0:
                    if aa[-1][0]-1 == e1 and aa[-1][1] == e2:
                        return len(aa)
                    if maze[aa[-1][0]-1][aa[-1][1]]=='O' and (aa[-1][0]-1,aa[-1][1]) not in aa:
                        aa.append((aa[-1][0] - 1, aa[-1][1]))
                        b.append(aa)
                #left
                aa=aaa[:]
                if aa[-1][1]-1>=0:
                    if aa[-1][0]==e1 and  aa[-1][1]-1==e2:
                        return len(aa)
                    if maze[aa[-1][0]][aa[-1][1]-1]=='O' and (aa[-1][0],aa[-1][1]-1) not in aa:
                        aa.append((aa[-1][0], aa[-1][1] - 1))
                        b.append(aa)
                #right
                aa=aaa[:]
                if aa[-1][1]+1<len(maze[0]):
                    if aa[-1][0] == e1 and aa[-1][1] +1 == e2:
                        return len(aa)
                    if maze[aa[-1][0]][aa[-1][1]+1]=='O' and (aa[-1][0],aa[-1][1]+1) not in aa:
                        aa.append((aa[-1][0], aa[-1][1] + 1))
                        b.append(aa)
                #down
                aa=aaa[:]
                if aa[-1][0]+1<len(maze):
                    if aa[-1][0]+1==e1 and aa[-1][1]==e2:
                        return len(aa)
                    if maze[aa[-1][0]+1][aa[-1][1]]=='O' and (aa[-1][0]+1,aa[-1][1]) not in aa:
                        aa.append((aa[-1][0] + 1, aa[-1][1]))
                        b.append(aa)
            a=b
        return -1
    maze = [['X', 'O', 'O', 'O', 'X'],
             ['X', 'O', 'O', 'O', 'X'],
             ['X', 'O', 'O', 'O', 'O'],
            ['X', 'O', 'S', 'O', 'E']]
    print find_shortest_path(maze)