Problem:


11 パズル

太郎君は 8 パズルが大得意で休み時間などにいつも友達に並び替えてもらって遊んでいます。そんなとき、友達から「もっと複雑なパズルは解ける?」と聞かれたのですが、他のパズルはやったことはありません。どうやらその友達は自作で 11 パズルを作っていたみたいです。そのパズルは以下のような形をしています。

11 パズルは 11 枚の正方形のカードと、図 1 のような形の枠を使って行います。最初に 11 枚のカードを枠に入れます。すると 2 カ所の空きスペースができますので、この空きスペースに隣接したカードを動かすことができます。これを繰り返し、カードをきれいに整列して、図 2 の完成型にすることが 11 パズルの目的です。

 太郎君はこのパズルに挑戦することにしました。ところが太郎君はこの 11 パズルをいとも簡単に解いてしまいました。そこで友達は「動かす数を一番少なくして解いてよ!」と無茶なことを言ってきました。太郎君は答えがわからないので、プログラムのできるあなたに 11 パズルを解くときの最小ステップ数を出すプログラムを作成してもらってから挑戦することにしました。このとき、2 カ所動かせるところがあるのですが、一つの数字を 1 スペース分移動させることを1ステップとして考えることとします。

11 パズルの初期状態を入力とし、11 パズルを解くときの最小ステップ数を出力するプログラムを作成してください。ただし、パズルを解くときの最小ステップ数が 20 ステップより多くかかってしまう場合は、「NA」と出力してください。パズルの状態は、一行目の情報から順に入力されるものとし、数字の 0 は空きスペースを表します。例えば、図 1 の状態を表す入力は以下のようになります。

6
2 1 3
10 5 7 0 8
9 4 11
0

Input

 複数のデータセットの並びが入力として与えられます。入力の終わりは-1ひとつの行で示されます。 各データセットは以下の形式で与えられます。

p1
p2 p3 p4
p5 p6 p7 p8 p9
p10 p11 p12
p13

i 行目にパズルの i 行目の情報 pi (0 ≤ pi ≤ 11) が空白区切りで与えられます。

データセットの数は 100 を超えません。

Output

データセット毎に、最小ステップ数または NA を１行に出力します。

Sample Input

2
1 0 3
4 5 6 7 8
9 0 11
10
0
1 2 3
4 5 6 7 8
9 10 11
0
0
11 10 9
8 7 6 5 4
3 2 1
0
-1

Output for the Sample Input

2
0
NA



Sample input:
2
1 0 3
4 5 6 7 8
9 0 11
10
0
1 2 3
4 5 6 7 8
9 10 11
0
0
11 10 9
8 7 6 5 4
3 2 1
0
-1


Sample output:
2
0
NA

Submission status: Wrong Answer

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

ANS_HASH=[hash([0,1,2,3,4,5,6,7,8,9,10,11,12]),hash([12,1,2,3,4,5,6,7,8,9,10,11,0])]          

while True:
    p=[input()]
    if p==[-1]:
        break
    for u in xrange(4):
        for pp in map(int,raw_input().split()):
            p.append(pp)
    p[p.index(0)]=12
    pq = PriorityQueue()
    pq.put([evaluate(p),hash(p),0])
    visited={}
    visited[hash(p)]=True
    ans=0 if hash(p) in ANS_HASH else "NA"
    #cur=[eva,hashkey,step]
    while not pq.empty():
        eva,cur_hash,cur_step=pq.get()
        cur_cell=dehash(cur_hash)
        if not (eva<20 and ans=="NA"):
            break
        for i in xrange(13):
            if cur_cell[i]==0 or cur_cell[i]==12:
                for ii in [LEFT,UP,RIGHT,DOWN]:
                    if not MOVE[i][ii]==-1:
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                        hashkey=hash(cur_cell)
                        if not hashkey in visited:
                            if hashkey in ANS_HASH:
                                ans=cur_step+1
                                break
                            pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                            visited[hashkey]=True
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
    print ans

Submission status: Wrong Answer

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

while True:
    p=[input()]
    if p==[-1]:
        break
    for u in xrange(4):
        for pp in map(int,raw_input().split()):
            p.append(pp)
    p[p.index(0)]=12
    pq=PriorityQueue()
    init_hash=hash(p)
    init_eva=evaluate(p)
    pq.put([init_eva,init_hash,0])
    visited={}
    visited[init_hash]=True
    ans=0 if init_eva==0 else "NA"
        #cur=[eva,hashkey,step]
    while not pq.empty():
        cur_eva,cur_hash,cur_step=pq.get()
        cur_cell=dehash(cur_hash)
        if not (cur_eva<20 and ans=="NA"):
            break
        for i in xrange(13):
            if cur_cell[i]==0 or cur_cell[i]==12:
                for ii in [LEFT,UP,RIGHT,DOWN]:
                    if not MOVE[i][ii]==-1:
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                        hashkey=hash(cur_cell)
                        if not hashkey in visited:
                            eva=evaluate(cur_cell)
                            if eva==0:
                                ans=cur_step+1
                                break
                            pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                            visited[hashkey]=True
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
    print ans

Submission status: Accepted

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

"""
MOVE[0][LEFT]=MOVE[1][LEFT]=MOVE[4][LEFT]=MOVE[9][LEFT]=MOVE[12][LEFT]=False
MOVE[0][UP]=MOVE[1][UP]=MOVE[3][UP]=MOVE[4][UP]=MOVE[8][UP]=False
MOVE[0][RIGHT]=MOVE[3][RIGHT]=MOVE[8][RIGHT]=MOVE[11][RIGHT]=MOVE[12][RIGHT]=False
MOVE[4][DOWN]=MOVE[8][DOWN]=MOVE[9][DOWN]=MOVE[11][DOWN]=MOVE[12][DOWN]=False
"""

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

ANS_HASH=[hash([0,1,2,3,4,5,6,7,8,9,10,11,12]),hash([12,1,2,3,4,5,6,7,8,9,10,11,0])]          

while True:
    p=[input()]
    if p==[-1]:
        break
    for u in xrange(4):
        for pp in map(int,raw_input().split()):
            p.append(pp)
    p[p.index(0)]=12
    pq = PriorityQueue()
    pq.put([evaluate(p),hash(p),0])
    visited={}
    visited[hash(p)]=True
    ans=0 if hash(p) in ANS_HASH else "NA"
    #cur=[eva,hashkey,step]
    while not pq.empty():
        unused,cur_hash,cur_step=pq.get()
        cur_cell=dehash(cur_hash)
        """
        print "STEP",cur_step
        print [cur_cell[0]]
        print cur_cell[1:4]
        print cur_cell[4:9]
        print cur_cell[9:12]
        print [cur_cell[12]]
        print
        """
        if not (cur_step<20 and ans=="NA"):
            break
        for i in xrange(13):
            if cur_cell[i]==0 or cur_cell[i]==12:
                #print cur_cell[i]
                for ii in [LEFT,UP,RIGHT,DOWN]:
                    #print ii,
                    if not MOVE[i][ii]==-1:
                        #print "MOVE"
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                        """
                        print "MOVING",ii
                        print [cur_cell[0]]
                        print cur_cell[1:4]
                        print cur_cell[4:9]
                        print cur_cell[9:12]
                        print [cur_cell[12]]
                        """
                        hashkey=hash(cur_cell)
                        if not hashkey in visited:
                            if hashkey in ANS_HASH:
                                ans=cur_step+1
                                break
                            pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                            visited[hashkey]=True
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                    else:
                        pass
                        #print 
    print ans

Submission status: Accepted

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

ANS_HASH=[hash([0,1,2,3,4,5,6,7,8,9,10,11,12]),hash([12,1,2,3,4,5,6,7,8,9,10,11,0])]          

while True:
    p=[input()]
    if p==[-1]:
        break
    for u in xrange(4):
        for pp in map(int,raw_input().split()):
            p.append(pp)
    p[p.index(0)]=12
    pq = PriorityQueue()
    pq.put([evaluate(p),hash(p),0])
    visited={}
    visited[hash(p)]=True
    ans=0 if hash(p) in ANS_HASH else "NA"
    #cur=[eva,hashkey,step]
    while not pq.empty():
        eva,cur_hash,cur_step=pq.get()
        cur_cell=dehash(cur_hash)
        if not (eva<=20 and ans=="NA"):
            break
        for i in xrange(13):
            if cur_cell[i]==0 or cur_cell[i]==12:
                for ii in [LEFT,UP,RIGHT,DOWN]:
                    if not MOVE[i][ii]==-1:
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                        hashkey=hash(cur_cell)
                        if not hashkey in visited:
                            if hashkey in ANS_HASH:
                                ans=cur_step+1
                                break
                            pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                            visited[hashkey]=True
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
    print ans

Submission status: Accepted

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

if __name__== "__main__":
    while True:
        p=[input()]
        if p==[-1]:
            break
        for u in xrange(4):
            for pp in map(int,raw_input().split()):
                p.append(pp)
        p[p.index(0)]=12
        pq=PriorityQueue()
        init_hash=hash(p)
        init_eva=evaluate(p)
        pq.put([init_eva,init_hash,0])
        visited={}
        visited[init_hash]=True
        ans=0 if init_eva==0 else "NA"
        count=0
        #cur=[eva,hashkey,step]
        while not pq.empty():
            count+=1
            cur_eva,cur_hash,cur_step=pq.get()
            cur_cell=dehash(cur_hash)
            if not (cur_eva<=20 and ans=="NA"):
                break
            for i in xrange(13):
                if cur_cell[i]==0 or cur_cell[i]==12:
                    for ii in [LEFT,UP,RIGHT,DOWN]:
                        if not MOVE[i][ii]==-1:
                            cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                            hashkey=hash(cur_cell)
                            if not hashkey in visited:
                                eva=evaluate(cur_cell)
                                if eva==0:
                                    ans=cur_step+1
                                    break
                                pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                                visited[hashkey]=True
                            cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
        print ans

Submission status: Accepted

Solution code:
from math import factorial
from Queue import PriorityQueue

FACTORIAL=[factorial(i) for i in xrange(13)]
LEFT,UP,RIGHT,DOWN=0,1,2,3
MOVE=[[0] for u in xrange(13)]
MOVE[0] =[-1,-1,-1, 2]
MOVE[1] =[-1,-1, 2, 5]
MOVE[2] =[ 1, 0, 3, 6]
MOVE[3] =[ 2,-1,-1, 7] 
MOVE[4] =[-1,-1, 5,-1]
MOVE[5] =[ 4, 1, 6, 9]
MOVE[6] =[ 5, 2, 7,10]
MOVE[7] =[ 6, 3, 8,11]
MOVE[8] =[ 7,-1,-1,-1]
MOVE[9] =[-1, 5,10,-1]
MOVE[10]=[ 9, 6,11,12]
MOVE[11]=[10, 7,-1,-1]
MOVE[12]=[-1,10,-1,-1]

def hash(cell):
    work = cell[:]
    hash = 0
    for i in xrange(12):
        hash += work[i] * FACTORIAL[13-1-i]
        for ii in xrange(i+1,13):
            if work[ii]>work[i]:
                work[ii]-=1
    return hash

def dehash(key):
    cell=[]
    for i in xrange(13):
        cell.append(key/FACTORIAL[13-1-i])
        key %= FACTORIAL[13-1-i]
    for i in xrange(13-1,-1,-1):
        for ii in xrange(i+1,13):
            if cell[i]<=cell[ii]:
                cell[ii]+=1
    return cell

def evaluate(cell):
    point=[[0,2],
           [1,1],[1,2],[1,3],
           [2,0],[2,1],[2,2],[2,3],[2,4],
           [3,1],[3,2],[3,3],
           [4,2]]
    eva=0
    for i in xrange(0,13):
        if not (cell[i]==0 or cell[i]==12):
            eva+=abs(point[cell[i]][0]-point[i][0])
            eva+=abs(point[cell[i]][1]-point[i][1])
    return eva

while True:
    p=[input()]
    if p==[-1]:
        break
    for u in xrange(4):
        for pp in map(int,raw_input().split()):
            p.append(pp)
    p[p.index(0)]=12
    pq=PriorityQueue()
    init_hash=hash(p)
    init_eva=evaluate(p)
    pq.put([init_eva,init_hash,0])
    visited={}
    visited[init_hash]=True
    ans=0 if init_eva==0 else "NA"
        #cur=[eva,hashkey,step]
    while not pq.empty():
        cur_eva,cur_hash,cur_step=pq.get()
        cur_cell=dehash(cur_hash)
        if not (cur_eva<=20 and ans=="NA"):
            break
        for i in xrange(13):
            if cur_cell[i]==0 or cur_cell[i]==12:
                for ii in [LEFT,UP,RIGHT,DOWN]:
                    if not MOVE[i][ii]==-1:
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
                        hashkey=hash(cur_cell)
                        if not hashkey in visited:
                            eva=evaluate(cur_cell)
                            if eva==0:
                                ans=cur_step+1
                                break
                            pq.put([evaluate(cur_cell)+cur_step+1,hashkey,cur_step+1])
                            visited[hashkey]=True
                        cur_cell[i],cur_cell[MOVE[i][ii]]=cur_cell[MOVE[i][ii]],cur_cell[i]
    print ans

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

comp = [(1, 1), (2, 1), (3, 1),
        (0, 2), (1, 2), (2, 2), (3, 2), (4, 2),
        (1, 3), (2, 3), (3, 3)]
numbers = range(11)
zeros = (11, 12)

def manhattan(v1, v2):
  x1, y1 = v1
  x2, y2 = v2
  return abs(x2 - x1) + abs(y2 - y1)

def heuristic(state):
  return sum([manhattan(state[i], comp[i]) for i in numbers])

def swaped(state, n1, n2):
  new_state = [i for i in state]
  new_state[n1], new_state[n2] = new_state[n2], new_state[n1]
  return tuple(new_state)

def main():
  while True:
    p1 = int(input())
    if p1 == -1:
      break
    l1 = [-1, -1, p1, -1, -1]
    l2 = [-1] + list(map(int, input().split())) + [-1]
    l3 = list(map(int, input().split()))
    l4 = [-1] + list(map(int, input().split())) + [-1]
    l5 = [-1, -1, int(input()), -1, -1]
    mp = [l1, l2, l3, l4, l5]
    init_state = [None] * 13
    for y in range(5):
      for x in range(5):
        if mp[y][x] != -1:
          if mp[y][x] == 0:
            if not init_state[11]:
              init_state[11] = (x, y)
            else:
              init_state[12] = (x, y)
          else:
            init_state[mp[y][x] - 1] = (x, y)
    init_state = tuple(init_state)
    dic = {}
    dic[init_state] = True
    que = []
    heappush(que, (heuristic(init_state) + 0, 0, init_state))
    while que:
      score, count, state = heappop(que)
      if score == count:
        print(count)
        break
  
      for z in zeros:
        for i in numbers:
          if manhattan(state[z], state[i]) == 1:
            new_state = swaped(state, i, z)
            if new_state not in dic:
              dic[new_state] = True
              new_score = heuristic(new_state) + count + 1
              if new_score <= 20:
                heappush(que, (new_score, count + 1, new_state))
    else:
      print("NA")

main()