贴一下拼多多笔试最后一题BFS的写法吧~感觉更符合菜鸟的思路

# -*- coding: utf-8 -*-
m,n=5,5
migong=[
list('02111'),
list('01a0A'),
list('01003'),
list('01001'),
list('01111')
]
for i in range(m):
    for j in range(n):
        if migong[i][j]=='2':
            begin=(i,j)
        if migong=='3':
            end=(i,j)
BFS=[(begin,[])]
pointsPassed=[begin]
stepCnt=0
while True:
    lastPoints=BFS
    t=[]
    flag=False
    for i in lastPoints:
        points=i[0]
        keys=i[1]
        if points[0]>=1:
            newX=points[0]-1
            newY=points[1]
            if migong[newX][newY] == '1' or migong[newX][newY] == '2':
                t.append(((newX,newY),keys))
            elif migong[newX][newY] == '0':
                pass
            elif 'a'<=migong[newX][newY]<='z':
                q=keys[:]
                q.append(migong[newX][newY])
                t.append(((newX,newY), q))
            elif 'A'<=migong[newX][newY]<='Z':
                if migong[newX][newY].lower() in keys:
                    t.append(((newX, newY), keys))
                else:
                    pass
            else:
                stepCnt+=1
                flag=True
                break
        if points[1]>=1:
            newX=points[0]
            newY=points[1]-1
            if migong[newX][newY] == '1' or migong[newX][newY] == '2':
                t.append(((newX,newY),keys))
            elif migong[newX][newY] == '0':
                pass
            elif 'a'<=migong[newX][newY]<='z':
                q=keys[:]
                q.append(migong[newX][newY])
                t.append(((newX,newY), q))
            elif 'A'<=migong[newX][newY]<='Z':
                if migong[newX][newY].lower() in keys:
                    t.append(((newX, newY), keys))
                else:
                    pass
            else:
                stepCnt+=1
                flag = True
                break
        if points[0]<m-1:
            newX=points[0]+1
            newY=points[1]
            if migong[newX][newY] == '1' or migong[newX][newY] == '2':
                t.append(((newX,newY),keys))
            elif migong[newX][newY] == '0':
                pass
            elif 'a'<=migong[newX][newY]<='z':
                q=keys[:]
                q.append(migong[newX][newY])
                t.append(((newX,newY), q))
            elif 'A'<=migong[newX][newY]<='Z':
                if migong[newX][newY].lower() in keys:
                    t.append(((newX, newY), keys))
                else:
                    pass
            else:
                stepCnt+=1
                flag = True
                break
        if points[1]<n-1:
            newX=points[0]
            newY=points[1]+1
            if migong[newX][newY] == '1' or migong[newX][newY] == '2':
                t.append(((newX,newY),keys))
            elif migong[newX][newY] == '0':
                pass
            elif 'a'<=migong[newX][newY]<='z':
                q=keys[:]
                q.append(migong[newX][newY])
                t.append(((newX,newY), q))
            elif 'A'<=migong[newX][newY]<='Z':
                if migong[newX][newY].lower() in keys:
                    t.append(((newX, newY), keys))
                else:
                    pass
            else:
                stepCnt+=1
                flag = True
                break
    if flag:
        break
    stepCnt+=1
    BFS=t[:]
print stepCnt