syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(11問目)

問題
Seven Puzzle

所感
・眠い
pythonのミュータブルオブジェクトで悩み時間を無駄にし虚無
・多分普通の幅優先探索だと思う
・もっといい解法があると思うの(このコードだとTLEになっちゃう)

コード
(これだとACできない...)

import copy
import queue
ans=[[0,1,2,3],[4,5,6,7]]

while True:
    try:
        P=list(map(int,input().split()))
    except:
        break
    p=[]
    serchDct={}

    Pstr=''.join(map(str,P))
    serchDct[Pstr]=0

    p.append(P[:4])
    p.append(P[4:])

    q=queue.Queue()
    q.put(p)

    while not q.empty():
        nowp=q.get()
        nowP=nowp[0]+nowp[1]
        nowStr=''.join(map(str,nowP))
        if nowp==ans:
            break

        i,j=nowP.index(0)//4,nowP.index(0)%4
        for di,dj in [[1,0],[0,1],[-1,0],[0,-1]]:
            if 0<=i+di<2 and 0<=j+dj<4:
                nextp=copy.deepcopy(nowp)
                nextp[i][j],nextp[i+di][j+dj]=nextp[i+di][j+dj],nextp[i][j]
                nextP=nextp[0]+nextp[1]
                nextStr=''.join(map(str,nextP))

                if (nextStr in serchDct)==False:
                    serchDct[nextStr]=serchDct[nowStr]+1
                    q.put(nextp)
    print(serchDct[nowStr])