蓝桥杯历届试题-九宫重排-题解（Python代码）（双向bfs）

解题思路:根据大佬改编的

注意事项:

参考代码:

def check(x,y):
        return x<3 and x>=0 and y<3 and y>=0
def toMatrix(strn):
        global m
        m=[[None]*3 for i in range(3)]
        for i in range(len(strn)):
                m[i//3][i%3]=strn[i]
def tostring():
        global m
        l=''
        for i in range(3):
                for j in range(3):
                        l+=m[i][j]
        return l
        
def dbfs():
        
        global m
        dira=[[0, 1],[0, -1],[1, 0],[-1, 0]]
        q1=[]
        q2=[]
        dis={}
        vis={}
        q1.append(first)
        dis[first]=1
        vis[first]=1
        q2.append(last)
        dis[last]=1
        vis[last]=2
        while len(q1)>0 and len(q2)>0:
                if len(q1)<len(q2):
                        str1=q1.pop(0)
                        flag=1
                else:
                        str1=q2.pop(0)
                        flag=2
                toMatrix(str1)
                for i in range(3):
                        for j in range(3):
                                if m[i][j]=='.':
                                        x=i
                                        y=j
             
                for i in range(4):
                        tx=x+dira[i][0]
                        ty=y+dira[i][1]
                        if check(tx,ty):
                                m[x][y],m[tx][ty]=m[tx][ty],m[x][y]
                                str2=tostring()
                                if not str2 in dis.keys():
                                        dis[str2]=dis[str1]+1
                                        vis[str2]=vis[str1]
                                        if flag==1:
                                                q1.append(str2)
                                        elif flag==2:
                                                q2.append(str2)
                                else:
                                        if vis[str1]+vis[str2]==3:
                                                ans=dis[str1]+dis[str2]-1
                                                return ans
                                m[x][y],m[tx][ty]=m[tx][ty],m[x][y]
        return -1
first=input().strip()
last=input().strip()
if last==first:
        print('0')
else:
        print(dbfs())