113 lines
3.6 KiB
Python
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)
|