Извинения за довольно длинный переулок.У меня было время убить в поезде.
Я предполагаю, что вам нужен ориентированный граф, представляющий все пути, ведущие в сторону от вашей начальной позиции (в отличие от графа, представляющего лабиринт, который когда-то можетиспользуйте для решения произвольных начальных / конечных положений).
(Не обижайте, но) это звучит как домашняя работа или, по крайней мере, задача, которая очень подходит для домашней работы.Имея это в виду, следующее решение фокусируется на простоте, а не на производительности или элегантности.
Подход
Один простой способ сделать это - сначала сохранить карту в более удобном для навигации формате.затем, начиная с начального узла, выполните следующие действия:
- ищите соседей (сверху, снизу, слева, справа)
- для каждого соседа:
- еслиэто не возможный путь, игнорируйте
- , если мы обрабатывали этот узел раньше, игнорируем
- , добавьте этот узел как ребро и поместите его в очередь (не в стек, подробнее об этомпозже) для дальнейшей обработки
- для каждого узла в очереди / стеке повторите процедуру с шага 1.
(см. пример реализации ниже)
На этом этапе вы получите направленный ациклический граф (DAG) с начальным узлом в верхней части дерева и конечным узлом в качестве одного из листьев.Решить это было бы легко на этом этапе.См. этот ответ по решению лабиринта, представляющего собой граф .
Возможная оптимизация при построении графа состояла бы в том, чтобы остановиться, как только будет найдена конечная точка.В итоге вы получите неполный график, но если вас беспокоит только окончательное решение, это не имеет значения.
стек или очередь?
Обратите внимание, что использование стека (первый в последнем выходе) будет означать построение графика способом глубина-сначала при использовании очереди (первый-первый-первый) приведет к подходу в ширину .
Как правило, вы хотите использовать очередь (шириной в первую очередь, если вы хотите найти кратчайший путь. Рассмотрите следующую карту:
START
######## ######
######## ######
### b a ######
### ## ######
### ## e ######
### c d ######
######## ######
######## END
#################
Если путь проходит сначала в глубинуи в ответвлении a вы выбираете путь a->b до a->e, в результате вы получаете график:
START
|
a
/ \
b e <-- end, since d already visited
|
c
|
d
\
END
Однако при использовании подхода в ширину получится путь a->eчерез узел d ранее, что привело к более короткому графику и лучшему решению:
START
|
a
/ \
b e
| |
c d
|
END
Пример кода
Пример ввода при условии:
..........
#########.
..........
.#########
......#...
#####...#.
##...####.
##.#......
...#######
e = (0,0)
s = (8,0)
ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Следующий код написан для ясности, а не для скорости. Он не полностью протестирован, поэтому нет гарантии правильности, но он должен дать вам представление о том, что возможно.
Мы предполагаем, чтовходной файл отформатирован согласованно. Большинство проверок на ошибки оставлено для краткости.
# regex to extract start/end positions
import re
re_sepos = re.compile("""
^([se])\s* # capture first char (s or e) followed by arbitrary spaces
=\s* # equal sign followed by arbitrary spaces
\( # left parenthesis
(\d+),(\d+) # capture 2 sets of integers separated by comma
\) # right parenthesis
""", re.VERBOSE)
def read_maze(filename):
"""
Reads input from file and returns tuple (maze, start, end)
maze : dict holding value of each maze cell { (x1,y1):'#', ... }
start: start node coordinage (x1,y1)
end : end node coordinate (x2,y2)
"""
# read whole file into a list
f = open(filename, "r")
data = f.readlines()
f.close()
# parse start and end positions from last 2 lines
pos = {}
for line in data[-2:]:
match = re_sepos.match(line)
if not match:
raise ValueError("invalid input file")
c,x,y = match.groups() # extract values
pos[c] = (int(x),int(y))
try:
start = pos["s"]
end = pos["e"]
except KeyError:
raise ValueError("invalid input file")
# read ascii maze, '#' for wall '.' for empty slor
# store as maze = { (x1,y1):'#', (x2,y2):'.', ... }
# NOTE: this is of course not optimal, but leads to a simpler access later
maze = {}
for line_num, line in enumerate(data[:-3]): # ignore last 3 lines
for col_num, value in enumerate(line[:-1]): # ignore \n at end
maze[(line_num, col_num)] = value
return maze, start, end
def maze_to_dag(maze, start, end):
"""
Traverses the map starting from start coordinate.
Returns directed acyclic graph in the form {(x,y):[(x1,y1),(x2,y2)], ...}
"""
dag = {} # directed acyclic graph
queue = [start] # queue of nodes to process
# repeat till queue is empty
while queue:
x,y = queue.pop(0) # get next node in queue
edges = dag[(x,y)] = [] # init list to store edges
# for each neighbour (top, bottom, left, right)
for coord in ((x,y-1), (x,y+1), (x-1,y), (x+1,y)):
if coord in dag.keys(): continue # visited before, ignore
node_value = maze.get(coord, None) # Return None if outside maze
if node_value == ".": # valid path found
edges.append(coord) # add as edge
queue.append(coord) # push into queue
# uncomment this to stop once we've found the end point
#if coord == end: return dag
return dag
if __name__ == "__main__":
maze,start,end = read_maze("l4.txt")
dag = maze_to_dag(maze, start, end)
print dag