|
|
关于python广度搜索
广度搜索华容道最佳解法，我的代码如下
def bfs(start, end,rows,cols):
queue = []
queue2 = []
queue.append([start])
while True:
if not queue:
queue,queue2 = queue2,queue
if not queue:
return []
path = queue.pop(0)
node = path[-1]
# path found
if node == end:
return path
if not node in path[:-1]:
map=node[0]
x=node[1]
y=node[2]
#print(map)
if x>0:
# left
maplst=list(map)
#print(node)
maplst[2*y*cols+2*x]=maplst[2*y*cols+2*(x-1)]
maplst[2*y*cols+2*x+1]=maplst[2*y*cols+2*(x-1)+1]
maplst[2*y*cols+2*(x-1)]='0'
maplst[2*y*cols+2*(x-1)+1]='0'
temlst=[]
temlst.append(''.join(maplst))
temlst.append(x-1)
temlst.append(y)
temlst2=[]
temlst2.append(path)
temlst2.append(temlst)
queue2.append(temlst2)
if x<cols-1:
# right
maplst=list(map)
maplst[2*y*cols+2*x]=maplst[2*y*cols+2*(x+1)]
maplst[2*y*cols+2*x+1]=maplst[2*y*cols+2*(x+1)+1]
maplst[2*y*cols+2*(x+1)]='0'
maplst[2*y*cols+2*(x+1)+1]='0'
temlst=[]
temlst.append(''.join(maplst))
temlst.append(x+1)
temlst.append(y)
temlst2=[]
temlst2.append(path)
temlst2.append(temlst)
queue2.append(temlst2)
if y>0:
# up
maplst=list(map)
maplst[2*y*cols+2*x]=maplst[2*(y-1)*cols+2*x]
maplst[2*y*cols+2*x+1]=maplst[2*(y-1)*cols+2*x+1]
maplst[2*(y-1)*cols+2*x]='0'
maplst[2*(y-1)*cols+2*x+1]='0'
temlst=[]
temlst.append(''.join(maplst))
temlst.append(x)
temlst.append(y-1)
temlst2=[]
temlst2.append(path)
temlst2.append(temlst)
queue2.append(temlst2)
if y<rows-1:
# down
maplst=list(map)
maplst[2*y*cols+2*x]=maplst[2*(y+1)*cols+2*x]
maplst[2*y*cols+2*x+1]=maplst[2*(y+1)*cols+2*x+1]
maplst[2*(y+1)*cols+2*x]='0'
maplst[2*(y+1)*cols+2*x+1]='0'
temlst=[]
temlst.append(''.join(maplst))
temlst.append(x)
temlst.append(y+1)
temlst2=[]
temlst2.append(path)
temlst2.append(temlst)
queue2.append(temlst2)
返回的结果是
[[[[[[[[[['040103020506000708', 0, 2]], ['040103020506070008', 1, 2]], ['0401030
20006070508', 1, 1]], ['040103000206070508', 0, 1]], ['000103040206070508', 0, 0
]], ['010003040206070508', 1, 0]], ['010203040006070508', 1, 1]], ['010203040506
070008', 1, 2]], ['010203040506070800', 2, 2]]
我希望返回的是
[['040103020506000708', 0, 2], ['040103020506070008', 1, 2], ['040103020006070508', 1, 1], ['040103000206070508', 0, 1], ['000103040206070508', 0, 0], ['010003040206070508', 1, 0], ['010203040006070508', 1, 1], ['010203040506070008', 1, 2], ['010203040506070800', 2, 2]]
调试半天，不知问题何在？恳请高人指点
|
|
