Skip to content

Instantly share code, notes, and snippets.

@felix021 felix021/4x4 puzzle
Created Jan 25, 2014

Embed
What would you like to do?
一个简单的BFS问题的答案,题面在这里:https://www.v2ex.com/t/98224
#!/usr/bin/env python
#coding:utf-8
#problem description: https://www.v2ex.com/t/98224
start_node = dict(state='2011001100110011', row=0, col=0, prev=None);
target_state = '2101101001011010'
def swap(state, r1, c1, r2, c2):
m, n = list(sorted([r1 * 4 + c1, r2 * 4 + c2]))
return state[:m] + state[n] + state[m+1:n] + state[m] + state[n+1:]
q = [start_node]
visited = set(start_node['state'])
qi = 0
while qi < len(q):
cur = q[qi]
qi += 1
s, r, c = cur['state'], cur['row'], cur['col']
if s == target_state: #found
def trace(node):
if node['prev'] != None:
trace(node['prev'])
else:
return
r1, c1 = node['prev']['row'], node['prev']['col']
r2, c2 = node['row'], node['col']
if r2 == r1 - 1:
print 'U', #'上',
elif r2 == r1 + 1:
print 'D', #'下',
elif c2 == c1 - 1:
print 'L', #'左',
else:
print 'R', #'右',
trace(cur)
break
def move(row, col):
if row >= 0 and row < 4 and col >= 0 and col < 4:
state = swap(s, r, c, row, col)
if state not in visited:
visited.add(state)
q.append(dict(state=state, row=row, col=col, prev=cur))
move(r - 1, c)
move(r + 1, c)
move(r, c - 1)
move(r, c + 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.