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: Wrong Answer

Solution code:
D={}
def f(A):
  def f1(x):
    tx=tuple(x)
    if tx in D: return
    SP.append(x)
    D[tx]=c+1
    return
  SP=[]
  if A==range(8): return 0
  SP.append(A)
  D[tuple(A)]=0
  while SP:
    a=SP.pop(0)
    c=D[tuple(a)]
    p=a.index(0)
    for i in range(4):
      x=a[:]
      dp=0
      if i==0 and p%4<3: dp=1
      elif i==1 and p%4>0: dp=-1
      elif i==2 and p<4: dp=4
      elif i==3 and p>3: dp=-4
      if dp==0: continue
      x[p],x[p+dp]=x[p+dp],x[p]
      if x==range(8): return c+1
      f1(x)

import sys
A=[]
for x in sys.stdin:
  A=map(int,x.split(" "))
  print f(A)

Submission status: Wrong Answer

Solution code:
D={}
def f(A):
  def f1(x):
    tx=tuple(x)
    if tx in D: return
    SP.append(x)
    D[tx]=c+1
    return
  d={}
  SP=[]
  if A==range(8): return 0
  SP.append(A)
  D[tuple(A)]=0
  while SP:
    a=SP.pop(0)
    c=D[tuple(a)]
    p=a.index(0)
    for i in range(4):
      x=a[:]
      dp=0
      if i==0 and p%4<3: dp=1
      elif i==1 and p%4>0: dp=-1
      elif i==2 and p<4: dp=4
      elif i==3 and p>3: dp=-4
      if dp==0: continue
      x[p],x[p+dp]=x[p+dp],x[p]
      if x==range(8): return c+1
      f1(x)

import sys
A=[]
for x in sys.stdin:
  A=map(int,x.split(" "))
  print f(A)

Submission status: Wrong Answer

Solution code:
import copy
goal = [0,1,2,3,4,5,6,7]
swap = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,6],[6,3]]
while 1:
    try:
        que = [map(int,raw_input().split())]
        done = []
        ans = 0
        while que:
            nque = []
            pzl = que.pop(0)
            if pzl == goal: break
            p = pzl.index(0)
            for q in swap[pzl.index(0)]:
                pzl1 = pzl[:]
                pzl1[p],pzl1[q] = pzl1[q],pzl1[p]
                if pzl1 not in done:
                    done.append(pzl1)
                    nque.append(pzl1)
            ans += 1
            que = copy.deepcopy(nque)
        print ans
    except:
        break

Submission status: Wrong Answer

Solution code:
import copy
goal = [0,1,2,3,4,5,6,7]
swap = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,6],[6,3]]
while 1:
    try:
        que = [map(int,raw_input().split())]
        done = copy.deepcopy(que)
        ans = 0
        while que:
            nque = []
            pzl = que.pop(0)
            if pzl == goal: break
            p = pzl.index(0)
            for q in swap[pzl.index(0)]:
                pzl1 = pzl[:]
                pzl1[p],pzl1[q] = pzl1[q],pzl1[p]
                if pzl1 not in done:
                    done.append(pzl1)
                    nque.append(pzl1)
            ans += 1
            que = copy.deepcopy(nque)
        print ans
    except:
        break

Submission status: Wrong Answer

Solution code:
import copy
goal = [0,1,2,3,4,5,6,7]
swap = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,7],[6,3]]
while 1:
    try:
        que = [map(int,raw_input().split())]
        done = copy.deepcopy(que)
        ans = 0
        while que:
            nque = []
            pzl = que.pop(0)
            if pzl == goal: break
            p = pzl.index(0)
            for q in swap[pzl.index(0)]:
                pzl1 = pzl[:]
                pzl1[p],pzl1[q] = pzl1[q],pzl1[p]
                if pzl1 not in done:
                    done.append(pzl1)
                    nque.append(pzl1)
            ans += 1
            que = copy.deepcopy(nque)
        print ans
    except:
        break

Submission status: Wrong Answer

Solution code:
import sys
memo = {}
sys.setrecursionlimit(40320)
def swap(state, a, b):
    state[a], state[b] = state[b], state[a]
def dfs(state, pos, c):
    key = "".join(map(str, state))
    if memo.has_key(key):
        return memo[key]
    memo[key] = c
    if pos!=0 and pos!=4:
        swap(state, pos-1, pos)
        dfs(state, pos-1, c+1)
        swap(state, pos-1, pos)
    if pos!=3 and pos!=7:
        swap(state, pos+1, pos)
        dfs(state, pos+1, c+1)
        swap(state, pos+1, pos)
    if pos<4:
        swap(state, pos+4, pos)
        dfs(state, pos+4, c+1)
        swap(state, pos+4, pos)
    else:
        swap(state, pos-4, pos)
        dfs(state, pos-4, c+1)
        swap(state, pos-4, pos)
    return c

dfs(range(8), 0, 0)
while True:
    try:
        state = raw_input().replace(" ","")
        print memo[state]
    except:
        break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(50000)

def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

def cstr(a, b, str):
    return str[0:a] + str[b] + str[a+1:b] + str[a] + str[b+1:]

def makeTable(table, str, cnt):

    if str in table:
        return
    table.update({str:cnt})

    i = str.find("0")
    if i > 0:
        makeTable(table, cstr(i-1,i,str), cnt+1)
    if i + 1 < 8:
        makeTable(table, cstr(i, i+1, str), cnt+1)
    if i < 4:
        makeTable(table, cstr(i, i+4, str), cnt+1)
    else:
        makeTable(table, cstr(i-4, i, str), cnt+1)

#table = {"01234567":999}
table = {}
makeTable(table, "01234567", 0)

N = list(get_input())
for l in range(len(N)):
    print(table[N[l].replace(" ","")])

Submission status: Time Limit Exceeded

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

import copy,sys

def solve(pieace):
	history,frontier = set(),set()
	frontier.add(tuple(pieace))
	target_list = list(range(8))

	step = 0
	while True:
		next_frontier = set()
		for pieace in frontier:
			if all(x==y for x,y in zip(pieace,target_list)):
#				print([(x,y) for x,y in zip(pieace,target_list)])
				return step
			zero_position = pieace.index(0)
			relative = zero_position%4

			new_peiace = list(copy.deepcopy(pieace))
			new_peiace[relative],new_peiace[relative+4] = new_peiace[relative+4],new_peiace[relative]
			new_peiace = tuple(new_peiace)
			if new_peiace not in history:
				next_frontier.add(new_peiace)

			if relative in [0,1,2]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position+1] = new_peiace[zero_position+1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in history:
					next_frontier.add(new_peiace)
			if relative in [1,2,3]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position-1] = new_peiace[zero_position-1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in history:
					next_frontier.add(new_peiace)
		history |= frontier
		frontier = next_frontier
		step += 1

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

if __name__=='__main__':
	main()

Submission status: Time Limit Exceeded

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

import copy,sys

def solve(pieace):
	target_list = list(range(8))

	frontier,previous_frontier = set(),set()
	frontier.add(tuple(pieace))

	for step in range(10*10):
		next_frontier = set()
		for pieace in frontier:
			if all(x==y for x,y in zip(pieace,target_list)):	return step
			zero_position = pieace.index(0)
			relative = zero_position%4

			new_peiace = list(copy.deepcopy(pieace))
			new_peiace[relative],new_peiace[relative+4] = new_peiace[relative+4],new_peiace[relative]
			new_peiace = tuple(new_peiace)
			if new_peiace not in previous_frontier:
				next_frontier.add(new_peiace)

			if relative in [0,1,2]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position+1] = new_peiace[zero_position+1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in previous_frontier:
					next_frontier.add(new_peiace)

			if relative in [1,2,3]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position-1] = new_peiace[zero_position-1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in previous_frontier:
					next_frontier.add(new_peiace)

		previous_frontier = frontier
		frontier = next_frontier

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

if __name__=='__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
while True:
	try:
		input()
		print(0)
	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: Time Limit Exceeded

Solution code:
while True:
	try:
		line = input().strip()
		if len(line)==0:break
		print(0)
	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: Time Limit Exceeded

Solution code:
from collections import deque
import copy
while True:
    try:
        P_dic = {}
        P_que = deque([])
        time = 0
        p_lis = list(map(int,input().split()))
        p_lis = [p_lis[0:4],p_lis[4:8]]

        P_que.append([time,p_lis])
        P_dic[tuple(p_lis[0] + p_lis[1])] = time

        while True:
            now_list = list(P_que.popleft())
            
            now_time = now_list[0]
            now_stat = copy.deepcopy(now_list[1])

            if now_stat == [[0,1,2,3],[4,5,6,7]]:
                print(now_time)
                break
            
            if 0 in now_stat[0]:
                zpos = [0,now_stat[0].index(0)]
            else:
                zpos = [1,now_stat[1].index(0)]

            state_c = copy.deepcopy(now_stat)
            #print(now_stat,1111)

            state_c[zpos[0]][zpos[1]],state_c[(zpos[0] + 1) % 2][zpos[1]] = state_c[(zpos[0] + 1) % 2][zpos[1]],state_c[zpos[0]][zpos[1]]
            #print(now_list,2222)
                    
            if not (tuple(state_c[0] + state_c[1])) in P_dic:
                P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                P_que.append([now_time + 1,state_c])

                

            
            
            
            if zpos == [0,0]:
                state_c = copy.deepcopy(now_stat)
                state_c[0][0] = state_c[0][1]
                state_c[0][1] = 0
                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                

            elif zpos == [1,0]:

                state_c = copy.deepcopy(now_stat)
                state_c[1][0] = state_c[1][1]
                state_c[1][1] = 0
                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
               
            elif zpos == [0,3]:
                state_c = copy.deepcopy(now_stat)
                state_c[0][3] = state_c[0][2]
                state_c[0][2] = 0
                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                
                
            elif zpos == [1,3]:
               
                state_c = copy.deepcopy(now_stat)
                state_c[1][3] = state_c[1][2]
                state_c[1][2] = 0
                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
               
            else:
                state_c = copy.deepcopy(now_stat)
                #print(state_c,"b")
                state_c[zpos[0]][zpos[1]],state_c[zpos[0]][zpos[1] + 1] = state_c[zpos[0]][zpos[1] + 1],state_c[zpos[0]][zpos[1]]

                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                state_c = copy.deepcopy(now_stat)
                #print(state_c,zpos)
                state_c[zpos[0]][zpos[1]],state_c[zpos[0]][zpos[1] - 1] = state_c[zpos[0]][zpos[1] - 1],state_c[zpos[0]][zpos[1]]
                #print(state_c,now_time)
                if not (tuple(state_c[0] + state_c[1])) in P_dic:
                    P_dic[tuple(state_c[0] + state_c[1])] = now_time + 1
                    P_que.append([now_time + 1,state_c])
               
            if len(P_que) == 0:
                print("No")
                break
                
                
            
        
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
while True:
    try:
        P_dic = {}
        P_que = deque([])
        time = 0
        p_lis = list(map(int,input().split()))

        P_que.append([time,p_lis])
        P_dic[tuple(p_lis)] = time

        while True:
            now_list = P_que.popleft()
            now_time = now_list[0]
            now_stat = list(now_list[1])

            if now_stat == [0,1,2,3,4,5,6,7]:
                print(now_time)
                break
            
            zpos = now_stat.index(0)
        

            state_c = list(now_stat)
            state_c[zpos],state_c[(zpos + 4) % 8] = state_c[(zpos + 4) % 8],state_c[zpos]

                    
            if not (tuple(state_c)) in P_dic:
                P_dic[tuple(state_c)] = now_time + 1
                P_que.append([now_time + 1,state_c])
            
            if zpos == 0 or zpos == 4:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos + 1] = state_c[zpos + 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
          
               
            elif zpos == 3 or zpos == 7:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos - 1] = state_c[zpos - 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                    
            else:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos - 1] = state_c[zpos - 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos + 1] = state_c[zpos + 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                
               
            if len(P_que) == 0:
                print("No")
                break
        
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
while True:
    try:
        P_dic = {}
        P_que = deque([])
        time = 0
        p_lis = list(map(int,input().split()))

        P_que.append([time,p_lis])
        P_dic[tuple(p_lis)] = time

        while True:
            now_list = P_que.popleft()
            now_time = now_list[0]
            now_stat = list(now_list[1])

            if now_stat == [0,1,2,3,4,5,6,7]:
                print(now_time)
                break
            
            zpos = now_stat.index(0)
        

            state_c = list(now_stat)
            state_c[zpos],state_c[(zpos + 4) % 8] = state_c[(zpos + 4) % 8],state_c[zpos]

                    
            if not (tuple(state_c)) in P_dic:
                P_dic[tuple(state_c)] = now_time + 1
                P_que.append([now_time + 1,state_c])
            
            if zpos == 0 or zpos == 4:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos + 1] = state_c[zpos + 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
          
               
            elif zpos == 3 or zpos == 7:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos - 1] = state_c[zpos - 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                    
            else:
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos - 1] = state_c[zpos - 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                state_c = list(now_stat)
                state_c[zpos],state_c[zpos + 1] = state_c[zpos + 1],state_c[zpos]
                if not (tuple(state_c)) in P_dic:
                    P_dic[tuple(state_c)] = now_time + 1
                    P_que.append([now_time + 1,state_c])
                
               
            if len(P_que) == 0:
                print("No")
                break
        
    except :
        break

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 00121: Seven Puzzle
#
import sys, math, os, copy

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

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


def checksum(board):
    return 10000 * int(''.join([str(_) for _ in board[0]])) + int(''.join([str(_) for _ in board[1]]))

def seven_puzzle(board):
    offsets = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    if board == target:
        return 0
    queue = [(0, board)]
    visited = set()
    queued = set([checksum(board)])
    while len(queue) > 0:
        steps, board = queue.pop(0)
        if board == target:
            return steps
        visited.add(checksum(board))
        if 0 in board[0]:
            row, col = 0, board[0].index(0)
        else:
            row, col = 1, board[1].index(0)
        for row_off, col_off in offsets:
            row2, col2 = row + row_off, col + col_off
            if 0 <= row2 < 2 and 0 <= col2 < 4:
                new_board = copy.deepcopy(board)
                new_board[row][col] = new_board[row2][col2]
                new_board[row2][col2] = 0
                cs = checksum(new_board)
                if cs not in visited and cs not in queued:
                    queued.add(cs)
                    queue.append((steps + 1, new_board[:]))

        
for line in sys.stdin:
    puzzle = [int(_) for _ in line.split()]
    print(seven_puzzle([puzzle[:4], puzzle[4:]]))

Submission status: Time Limit Exceeded

Solution code:
def fun(f,i,sw):
    ret=[]
    for s in sw:
        ii,ss=min(i,s),max(i,s)
        ret.append( f[:ii]+f[ss]+f[ii+1:ss]+f[ii]+f[ss+1:])
    return ret

swaplist=[[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,6,1],[5,7,2],[6,3]]
A={}
A[1234567]=0
ks=[1234567]
F=["01234567"]
n=0
while len(F)!=0:
    NF=[]
    n+=1
    for f in F:
        i=f.index('0')
        sw=swaplist[i]
        for g in fun(f,i,sw):
            if int(g) not in ks:
                A[int(g)]=n
                ks.append(int(g))
                NF.append(g)
    F=NF[:]
while(1):
    try:
        print A[int("".join(raw_input().split()))]
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
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])

Submission status: Time Limit Exceeded

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

d=(1,-1,4,-4)

def check(s):
    if s==map(str,range(8)):
        return True
    return False

def bfs(s):
    m=set()
    que=[]
    que.append(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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
from Queue import Queue

ANSWER = 1234567


def to_int(a):
    return int(''.join(a))


def to_array(i):
    a = list(str(i))
    if len(a) < 8:
        a = ['0'] + a
    return a


def next_position(a):
    i = a.index('0')
    if i < 4:
        # left
        if i - 1 >= 0:
            b = a[:]
            b[i] = b[i - 1]
            b[i - 1] = '0'
            yield to_int(b)

        # right
        if i + 1 < 4:
            b = a[:]
            b[i] = b[i + 1]
            b[i + 1] = '0'
            yield to_int(b)

        # down
        b = a[:]
        b[i] = b[i + 4]
        b[i + 4] = '0'
        yield to_int(b)

    else:
        # left
        if i - 1 > 3:
            b = a[:]
            b[i] = b[i - 1]
            b[i - 1] = '0'
            yield to_int(b)

        # right
        if i + 1 < 8:
            b = a[:]
            b[i] = b[i + 1]
            b[i + 1] = '0'
            yield to_int(b)

        # up
        b = a[:]
        b[i] = b[i - 4]
        b[i - 4] = '0'
        yield to_int(b)


while True:
    try:
        a = raw_input().split()

        memo = []
        queue = Queue()

        i = to_int(a)
        memo.append(i)
        queue.put((0, i))

        count = 0
        while not queue.empty():
            t = queue.get()
            if t[1] == ANSWER:
                count = t[0]
                break

            for j in next_position(to_array(t[1])):
                if j not in memo:
                    memo.append(j)
                    queue.put((t[0] + 1, j))

        print count

    except ValueError:
        break

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
MOVE = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[1,4,6],[2,5,7],[3,6]]
GOAL = "01234567"
def h(field):    
    ret = 0
    for p,n in enumerate(map(int,field)):
        ret += dist(p,n)
    return ret
def dist(num,place):
    return abs(num%4-place%4)+(num/5+place/5)%2 #width+height
def swap(field,a,b):
    tmp = [f for f in field]
    tmp[a],tmp[b] = tmp[b],tmp[a]
    return "".join(tmp)

while True:
    try:
        field = raw_input().replace(" ","")    
    except:
        break
    hq = []
    visited = {field:True}
    heappush(hq,[0,0,field])
    while len(hq) != 0:
        f,g,field = heappop(hq)
        if field == GOAL:
            print g
            break    
        a = field.find("0")
        for b in MOVE[a]:
            tmp = swap(field,a,b)
            if tmp not in visited:
                visited[tmp] = True
                heappush(hq,[h(field)+g,g+1,tmp])

Submission status: Memory Limit Exceeded

Solution code:
def fun(f,i,sw):
    ret=[]
    for s in sw:
        ii,ss=min(i,s),max(i,s)
        ret.append( f[:ii]+f[ss]+f[ii+1:ss]+f[ii]+f[ss+1:])
    return ret

swaplist=[[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,6,1],[5,7,2],[6,3]]
A=[9999999 for i in range(80000000)]
A[1234567]=0
F=["01234567"]
n=0
while len(F)!=0:
    NF=[]
    n+=1
    for f in F:
        i=f.index('0')
        sw=swaplist[i]
        for g in fun(f,i,sw):
            if A[int(g)]>n:
                A[int(g)]=n
                NF.append(g)
    F=NF[:]

while(1):
    try:
        print A[int("".join(raw_input().split()))]
    except:
        break

Submission status: Accepted

Solution code:
D={}
R=range(8)
def f1(i,p):
  dp=0
  if i==0 and p%4<3: dp=1
  elif i==1 and p%4>0: dp=-1
  elif i==2 and p<4: dp=4
  elif i==3 and p>3: dp=-4
  return dp
  
def f():
  global D
  D={tuple(R):0}
  SP=[R]
  while SP:
    a=SP.pop(0)
    c=D[tuple(a)]
    p=a.index(0)
    for i in range(4):
      dp=f1(i,p)
      if dp==0: continue
      x=a[:]
      x[p],x[p+dp]=x[p+dp],x[p]
      tx=tuple(x)
      if tx in D: continue
      SP.append(x)
      D[tx]=c+1
  return

import sys
f()
A=[]
for x in sys.stdin:
  A=map(int,x.split(" "))
  print D[tuple(A)]

Submission status: Accepted

Solution code:
D={}
R=range(8)
def f1(i,p):
  dp=0
  if i==0 and p%4<3: dp=1
  elif i==1 and p%4>0: dp=-1
  elif i==2 and p<4: dp=4
  elif i==3 and p>3: dp=-4
  return dp
  
def f():
  global D
  D={tuple(R):0}
  SP=[R]
  while SP:
    a=SP.pop(0)
    p=a.index(0)
    for i in R[:4]:
      dp=f1(i,p)
      if dp==0: continue
      x=a[:]
      x[p],x[p+dp]=x[p+dp],x[p]
      tx=tuple(x)
      if tx in D: continue
      SP.append(x)
      D[tx]=D[tuple(a)]+1
  return

import sys
f()
for x in sys.stdin:
  A=map(int,x.split(" "))
  print D[tuple(A)]

Submission status: Accepted

Solution code:
move = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,7],[6,3]]

def swap(ls,p,q):
    res = list(ls)
    res[p],res[q] = res[q],res[p]
    return "".join(res)

ans = {"01234567":0}
que = [["01234567",0]]
while que:
    pzl,count = que.pop(0)
    p = pzl.find("0")
    for q in move[p]:
        tmp = swap(pzl,p,q)
        if tmp not in ans:
            ans[tmp] = count+1
            que.append([tmp,count+1])

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

Submission status: Accepted

Solution code:
move = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,7],[6,3]]

ans = {"01234567":0}
que = [["01234567",0]]
while que:
    pzl,count = que.pop(0)
    p = pzl.find("0")
    for q in move[p]:
        a,b = min(p,q),max(p,q)
        tmp = pzl[:a]+pzl[b]+pzl[a+1:b]+pzl[a]+pzl[b+1:]
        if tmp not in ans:
            ans[tmp] = count+1
            que.append([tmp,count+1])

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

Submission status: Accepted

Solution code:
move = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,1,6],[5,2,7],[6,3]]
ans = {"01234567":0}
q = [["01234567",0]]
while q:
    p,c = q.pop(0)
    a = p.find("0")
    for b in move[a]:
        x,y = min(a,b),max(a,b)
        tmp = p[:x]+p[y]+p[x+1:y]+p[x]+p[y+1:]
        if tmp not in ans:
            ans[tmp] = c+1
            q.append([tmp,c+1])

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

Submission status: Accepted

Solution code:
import Queue
memo = {}
def swap(state, a, b):
    state2 = state[:]
    state2[a], state2[b] = state2[b], state2[a]
    return state2
gkey = lambda state: "".join(map(str, state))

que = Queue.Queue()

init = range(8)
que.put((init, 0, 0))
memo[gkey(init)] = 0
while not que.empty():
    state, pos, c = que.get()
    def next_state(nxt):
        state2 = swap(state, nxt, pos)
        key = gkey(state2)
        if not memo.has_key(key):
            memo[key] = c+1
            que.put((state2, nxt, c+1))
    if pos!=0 and pos!=4:
        next_state(pos-1)
    if pos!=3 and pos!=7:
        next_state(pos+1)
    if pos<4:
        next_state(pos+4)
    else:
        next_state(pos-4)
while True:
    try:
        print memo[raw_input().replace(" ", "")]
    except EOFError:
        break

Submission status: Accepted

Solution code:
from collections import deque

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
    }
    q = deque()
    q.append([ia, 0])
    while q:
        a, c = q.popleft()
        i = a.index(0)
        for j in swap[i]:
            na = a.copy()
            na[i], na[j] = na[j], na[i]
            if str(na) not in count:
                count[str(na)] = c + 1
                q.append([na, c+1])

    return count

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