Problem:


7 パズル

7 パズルは 8 つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれのカードには、互いに区別できるように 0, 1, 2, ..., 7 と番号がつけられています。枠には、縦に 2 個、横に 4 個のカードを並べることができます。

7 パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで 0 のカードだけは、上下左右に隣接するカードと位置を交換することができます。たとえば、枠の状態が図(a) のときに、0 のカードの右に隣接した、7 のカードと位置を交換すれば、図(b) の状態になります。あるいは、図(a) の状態から 0 のカードの下に隣接した 2 のカードと位置を交換すれば図(c) の状態になります。図(a) の状態で 0 のカードと上下左右に隣接するカードは 7 と 2 のカードだけなので、これ以外の位置の入れ替えは許されません。

ゲームの目的は、カードをきれいに整列して図(d) の状態にすることです。最初の状態を入力とし、カードをきれいに整列するまでに、必要な最小手数を出力するプログラムを作成してください。ただし、入力されたカードの状態からは図(d) の状態に移ることは可能であるとします。

   入力データは、1 行に 8 つの数字が空白区切りで与えられます。これらは、最初の状態のカードの並びを表します。例えば、図(a) の数字表現は0 7 3 4 2 5 1 6 に、図(c) は 2 7 3 4 0 5 1 6 となります。

図(a) 0 7 3 4 2 5 1 6 の場合
図(b) 7 0 3 4 2 5 1 6 の場合

図(c) 2 7 3 4 0 5 1 6 の場合
図(d) 0 1 2 3 4 5 6 7 (最終状態)

Input

上記形式で複数のパズルが与えられます。入力の最後まで処理してください。
与えられるパズルの数は 1,000 以下です。

Output

各パズルについて、最終状態へ移行する最小手数を１行に出力してください。

Sample Input

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Output for the Sample Input

0
1
28



Sample input:
0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


Sample output:
0
1
28

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

"""

def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate

def solve(seq):
	global step

	init_step = 0
	# let CACHE[0]==0 and calculate initilizing step size
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step
	return 0
"""

def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
#		print(solve(seq))
		print(0)
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

"""

def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate

def solve(seq):
	global step

	init_step = 0
	# let CACHE[0]==0 and calculate initilizing step size
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step
	return 0
"""

def main():
#	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
#		print(solve(seq))
		print(0)
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def main():
	line = input().strip()
	while line!='':
		print(0)
		line = input().strip()

if __name__=='__main__':
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

if __name__=='__main__':
	line = input().strip()
	while line!='':
		print(0)
		line = input().strip()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

line = input().strip()
while line!='':
	print(0)
	line = input().strip()

Submission status: Runtime Error

Solution code:
line = input().strip()
while line!='':
	print(0)
	line = input().strip()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def main():
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(0)
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
while True:
	line = input().strip()
	if len(line)==0:break
	print(0)

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
while 1:
    try:
        print ans[raw_input().replace(" ","")]
    except:
        break

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass
"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
m={}
try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

Submission status: Runtime Error

Solution code:
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}

try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

Submission status: Runtime Error

Solution code:
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	break

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass

Submission status: Runtime Error

Solution code:
from collections import deque
import copy

swap = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]


def bfs():
    ia = list(range(8))
    count = {str(ia): 0}
    que = deque()
    que.append((ia, 0))
    while len(que) != 0:
        state, cnt = que.popleft()
        # pos:0?????????
        pos = state.index(0)
        swap_target = swap[pos]
        for i in swap_target:
            tmp_state = copy.copy(state)
            tmp_state[i], tmp_state[pos] = tmp_state[pos], tmp_state[i]
            if str(tmp_state) not in count:
                count[str(tmp_state)] = cnt + 1
                que.append((tmp_state, cnt + 1))
    return count


if __name__ == '__main__':
    count = bfs()
    while True:
        prob = list(map(int, input().split()))
        print(count[str(prob)])

Submission status: Runtime Error

Solution code:
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input
 
X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
    v=q.pop(0)
    coor=m[''.join(v)][0]
    x=coor%X
    y=coor//X
    depth=m[''.join(v)][1]
    nextstr=''.join(v)
    if 0<x:
        v[coor],v[coor-1]=v[coor-1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'R']
        v[coor],v[coor-1]=v[coor-1],v[coor]
    if x<X-1:
        v[coor],v[coor+1]=v[coor+1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'L']
        v[coor],v[coor+1]=v[coor+1],v[coor]
    if 0<y:
        v[coor],v[coor-X]=v[coor-X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'D']
        v[coor],v[coor-X]=v[coor-X],v[coor]
    if y<Y-1:
        v[coor],v[coor+X]=v[coor+X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'U']
        v[coor],v[coor+X]=v[coor+X],v[coor]
 
try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    passfrom __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input
 
X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
    v=q.pop(0)
    coor=m[''.join(v)][0]
    x=coor%X
    y=coor//X
    depth=m[''.join(v)][1]
    nextstr=''.join(v)
    if 0<x:
        v[coor],v[coor-1]=v[coor-1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'R']
        v[coor],v[coor-1]=v[coor-1],v[coor]
    if x<X-1:
        v[coor],v[coor+1]=v[coor+1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'L']
        v[coor],v[coor+1]=v[coor+1],v[coor]
    if 0<y:
        v[coor],v[coor-X]=v[coor-X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'D']
        v[coor],v[coor-X]=v[coor-X],v[coor]
    if y<Y-1:
        v[coor],v[coor+X]=v[coor+X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'U']
        v[coor],v[coor+X]=v[coor+X],v[coor]
 
try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

Submission status: Runtime Error

Solution code:
class Puzzle:
    def __init__(self,panel,space,cnt):
        self.panel=panel
        self.space=space
        self.cnt=cnt

d=(1,-1,4,-4)
model=map(str,range(8)):
def check(s):
    if s==model
        return True
    return False

def bfs(s):
    m=set()
    que=[s]
    m.add(tuple(s.panel))
    while que!=[]:
        now=que[0]
        del que[0]
        if check(now.panel):
            return now.cnt
        idx1=now.space
        for i in range(4):
            idx2=idx1+d[i]
            if idx2<0 or idx2>7:
                continue
            if (idx1==3 and d[i]==1) or (idx1==4 and d[i]==-1):
                continue
            next_panel=now.panel[:]
            next_panel[idx2],next_panel[idx1]=now.panel[idx1],now.panel[idx2]
            next=Puzzle(next_panel,idx2,now.cnt+1)
            if tuple(next.panel) not in m:
                m.add(tuple(next.panel))
                que.append(next)
    return -1

while True:
    try:
        panel=raw_input().split()
    except EOFError:
        break
    space=panel.index("0")
    s=Puzzle(panel,space,0)
    ans=bfs(s)
    print ans

Submission status: Runtime Error

Solution code:
class Puzzle:
    def __init__(self,panel,space,cnt):
        self.panel=panel
        self.space=space
        self.cnt=cnt

d=(1,-1,4,-4)
model=map(str,range(8))
def check(s):
    if s==model
        return True
    return False

def bfs(s):
    m=set()
    que=[s]
    m.add(tuple(s.panel))
    while que!=[]:
        now=que[0]
        del que[0]
        if check(now.panel):
            return now.cnt
        idx1=now.space
        for i in range(4):
            idx2=idx1+d[i]
            if idx2<0 or idx2>7:
                continue
            if (idx1==3 and d[i]==1) or (idx1==4 and d[i]==-1):
                continue
            next_panel=now.panel[:]
            next_panel[idx2],next_panel[idx1]=now.panel[idx1],now.panel[idx2]
            next=Puzzle(next_panel,idx2,now.cnt+1)
            if tuple(next.panel) not in m:
                m.add(tuple(next.panel))
                que.append(next)
    return -1

while True:
    try:
        panel=raw_input().split()
    except EOFError:
        break
    space=panel.index("0")
    s=Puzzle(panel,space,0)
    ans=bfs(s)
    print ans