append/code/bisearch.py

113 lines
3.6 KiB
Python

def expandNode(node_set, path_set):
new_node_set = []
new_path_set = []
while node_set != []:
x = node_set[0][0]
y = node_set[0][1]
if maze[x+1][y] == '0':
new_node_set.append([x+1,y])
new_path_set.append(path_set[0]+[[x+1,y]])
expanded.add((x+1,y))
if maze[x-1][y] == '0':
new_node_set.append([x-1,y])
new_path_set.append(path_set[0]+[[x-1,y]])
expanded.add((x-1,y))
if maze[x][y+1] == '0':
new_node_set.append([x,y+1])
new_path_set.append(path_set[0]+[[x,y+1]])
expanded.add((x,y+1))
if maze[x][y-1] == '0':
new_node_set.append([x,y-1])
new_path_set.append(path_set[0]+[[x,y-1]])
expanded.add((x,y-1))
maze[x][y] = '1'
expanded.add((x,y))
del node_set[0]
del path_set[0]
return new_node_set[:], new_path_set[:]
# 读入迷宫数据
maze = []
with open('MazeData.txt', 'r') as f:
for eachLine in f:
line = []
for eachPos in eachLine:
if eachPos == '\n':
break
line.append(eachPos)
maze.append(line)
# 找到起点和终点坐标,并加入可扩展节点
row = len(maze)
col = len(maze[0])
node_from_start = []
path_from_start = []
node_from_end = []
path_from_end = []
expanded = set()
for i in range(row):
for j in range(col):
if maze[i][j] == 'S':
node_from_start.append([i,j])
path_from_start.append([[i, j]])
expanded.add((i,j))
if maze[i][j] == 'E':
node_from_end.append([i, j])
path_from_end.append([[i, j]])
expanded.add((i, j))
# 开始搜索,宽度优先,每次起点和终点所有节点拓展一步
find_ans = False
while 1:
# 无拓展节点,即无解。退出循环
if node_from_start == [] or node_from_end == []:
find_ans = False
break
# 拓展从起点出发的节点
node_from_start, path_from_start = expandNode(node_from_start, path_from_start)
# 如果从起点和终点出发的节点重复,则找到解,退出循环
for eachNode in node_from_start:
if eachNode in node_from_end:
find_ans = True
break
if find_ans:
break
# 拓展从终点出发的节点
node_from_end, path_from_end = expandNode(node_from_end, path_from_end)
# 如果从起点和终点出发的节点重复,则找到解,退出循环
for eachNode in node_from_start:
if eachNode in node_from_end:
find_ans = True
break
if find_ans:
break
if find_ans == False:
print('no answer for this maze')
else:
for eachNode in node_from_start:
if eachNode in node_from_end:
cross_node = eachNode
break
start_idx = node_from_start.index(cross_node)
end_idx = node_from_end.index(cross_node)
ans = path_from_start[start_idx][:-1] + path_from_end[end_idx][::-1]
print(len(expanded))
print(len(ans))
print(ans)
# 将解的路径输出成txt文件
# maze = []
# with open('MazeData.txt', 'r') as f:
# for eachLine in f:
# maze.append(eachLine)
# for i in range(row):
# for j in range(col):
# if [i,j] in ansL
# if (i,j) in expanded:
# maze[i] = maze[i][:j] + 'X' + maze[i][j+1:]
# with open('ans.txt', 'w') as f:
# for eachLine in maze:
# f.write(eachLine)