|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
急急急!求走过路过大佬们能否指点一下。DFS递归时老是出错,希望能用PYTHON写
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 1 1 0 0 0 1
1 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
随意定起点终点。我就想知道怎么个递归方法,希望大佬们能配上讲解! 磕头感谢!! (最好也能像我写的BFS样输出每一步,没有也行)
下面是我自己码的BFS代码分享给大家。
#! /usr/bin/env python
FILE_NAME = " "
START_X = 2
START_Y = 2
END_X = 7
END_Y = 2
class Node:
def __init__(self, x, y, myId, parentId):
self.x = x
self.y = y
self.myId = myId
self.parentId = parentId
def dump(self):
print("---------- x "+str(self.x)+\
" | y "+str(self.y)+\
" | id "+str(self.myId)+\
" | parentId "+str(self.parentId))
nodes = []
init = Node(START_X, START_Y, 0, -2)
# init.dump()
nodes.append(init)
charMap = []
def dumpMap():
for line in charMap:
print (line)
with open(FILE_NAME) as f:
line = f.readline()
while line:
charLine = line.strip().split(',')
charMap.append(charLine)
line = f.readline()
charMap[START_X][START_Y] = '3'
charMap[END_X][END_Y] = '4'
dumpMap()
done = False
goalParentId = -1
while not done:
print("--------------------- number of nodes: "+str(len(nodes)))
for node in nodes:
node.dump()
# up
tmpX = node.x - 1
tmpY = node.y
if( charMap[tmpX][tmpY] == '4' ):
print("up: GOALLLL!!!")
goalParentId = node.myId
done = True
break
elif ( charMap[tmpX][tmpY] == '0' ): # 这里不能用else,因为 ‘1’ 墙壁会出错
print("up: mark visited")
newNode = Node(tmpX, tmpY, len(nodes), node.myId)
charMap[tmpX][tmpY] = '2'
nodes.append(newNode)
# down
tmpX = node.x + 1
tmpY = node.y
if( charMap[tmpX][tmpY] == '4' ):
print("down: GOALLLL!!!")
goalParentId = node.myId
done = True
break
elif ( charMap[tmpX][tmpY] == '0' ):
print("down: mark visited")
newNode = Node(tmpX, tmpY, len(nodes), node.myId)
charMap[tmpX][tmpY] = '2'
nodes.append(newNode)
# right
tmpX = node.x
tmpY = node.y + 1
if( charMap[tmpX][tmpY] == '4' ):
print("right: GOALLLL!!!")
goalParentId = node.myId
done = True
break
elif ( charMap[tmpX][tmpY] == '0' ):
print("right : mark visited")
newNode = Node(tmpX, tmpY, len(nodes), node.myId)
charMap[tmpX][tmpY] = '2'
nodes.append(newNode)
# left
tmpX = node.x
tmpY = node.y - 1
if( charMap[tmpX][tmpY] == '4' ):
print("left: GOALLLL!!!")
goalParentId = node.myId
done = True
break
elif ( charMap[tmpX][tmpY] == '0' ):
print("left: mark visited")
newNode = Node(tmpX, tmpY, len(nodes), node.myId)
charMap[tmpX][tmpY] = '2'
nodes.append(newNode)
dumpMap()
print("%%%%%%%%%%%%%%%%%%%")
ok = False
while not ok:
for node in nodes:
if( node.myId == goalParentId ):
node.dump()
goalParentId = node.parentId
if( goalParentId == -2):
print("%%%%%%%%%%%%%%%%%2")
ok = True
这个用DFS有点难....
因为它上下级关系不明确,就是很难制定一个好的深搜顺序
关于如何确定选项的优先级,这里应该不是最优解,但是时间有限,这样也行
望采纳
- text = []
- f = open('puzzle.txt')
- content = f.read().split('\n')
- for each_line in content:
- temp = []
- for i in each_line.split():
- temp.append(int(i))
- text.append(temp)
- p = [] #跟踪进度
- final_p = [] #储存目前最优路径
- l = 255 #储存步数
- start_x = int(input('输入起始行:'))
- start_y = int(input('输入起始列:'))
- end_x = int(input('输入终止行:'))
- end_y = int(input('输入终止列:'))
- #获取前进方向顺序。并非最优解。
- #从当前位置直接指向目标位置,使用右手定则。
- class Dir(list):
- def __init__(self, x, y):
- if end_x > x:
- dx = 1
- elif end_x < x:
- dx = -1
- else:
- dx = 0
- if end_y > y:
- dy = 1
- elif end_x < y:
- dy = -1
- else:
- dy = 0
- bas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
- temp = [(dx, 0),(0, dy),(-dx, 0),(0, -dy)]
- for each in temp:
- if each == (0, 0):
- continue
- elif each not in self:
- self.append(each)
- for each in bas:
- if each not in self:
- self.append(each)
- def dfs(x, y):
- global text, p, l, final_p
- if len(p) > l:
- return
- p.append((x, y))
- text[x][y] = -1
- if x == end_x and y == end_y:
- l = len(p)
- final_p = p[:]
- text[x][y] = 0
- p.remove((x, y))
- return
- for each in Dir(x, y):
- temp_x = x + each[0]
- temp_y = y + each[1]
- if check(temp_x, temp_y):
- dfs(temp_x, temp_y)
- p.remove((x, y))
- return
- #检查输入坐标是否已遍历或被阻挡
- def check(x, y):
- if x > len(text)-1 or x < 0 or\
- y > len(text[x])-1 or y < 0 or\
- text[x][y]:
- return False
- else:
- return True
- if __name__ == '__main__':
- dfs(start_x, start_y)
- if final_p:
- print(final_p)
- else:
- print('无法到达')
-
复制代码
|
|