39 lines
1.3 KiB
Python
39 lines
1.3 KiB
Python
file = './ex.txt'
|
|
#file = './ex2.txt'
|
|
#file = './input.txt'
|
|
|
|
from heapq import heappush, heappop
|
|
|
|
def solve_reindeer_maze(maze):
|
|
start = next((i, j) for i, row in enumerate(maze) for j, cell in enumerate(row) if cell == 'S')
|
|
end = next((i, j) for i, row in enumerate(maze) for j, cell in enumerate(row) if cell == 'E')
|
|
|
|
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
|
|
heap = [(0, start[0], start[1], 0)]
|
|
visited = set()
|
|
|
|
while heap:
|
|
score, row, col, direction = heappop(heap)
|
|
|
|
if (row, col) == end:
|
|
return score
|
|
|
|
if (row, col, direction) in visited:
|
|
continue
|
|
|
|
visited.add((row, col, direction))
|
|
|
|
for new_direction in range(4):
|
|
new_row, new_col = row + directions[new_direction][0], col + directions[new_direction][1]
|
|
if 0 <= new_row < len(maze) and 0 <= new_col < len(maze[0]) and maze[new_row][new_col] != '#':
|
|
new_score = score + 1
|
|
if new_direction != direction:
|
|
new_score += 1000
|
|
heappush(heap, (new_score, new_row, new_col, new_direction))
|
|
|
|
return float('inf')
|
|
# Einlesen des Labyrinths und Lösen
|
|
maze = [list(line.strip()) for line in open(file, 'r')]
|
|
result = solve_reindeer_maze(maze)
|
|
print(f"Die niedrigste mögliche Punktzahl ist: {result}")
|