import numpy as np
class Labyrinth:
def __init__(self, shape, start, end):
self.shape = shape
self.start = start
self.end = end
self.grid = np.zeros(shape, dtype=np.int8)
def add_wall(self, pos):
self.grid[pos[0], pos[1]] = 1
def is_valid_pos(self, pos):
return (pos[0] >= 0 and pos[0] < self.shape[0] and
pos[1] >= 0 and pos[1] < self.shape[1] and
self.grid[pos[0], pos[1]] == 0)
class Navigator:
def __init__(self, labyrinth):
self.labyrinth = labyrinth
def solve(self):
path = []
visited = set()
self._dfs(self.labyrinth.start, path, visited)
return path
def _dfs(self, pos, path, visited):
if pos == self.labyrinth.end:
path.append(pos)
return True
if pos in visited:
return False
visited.add(pos)
path.append(pos)
for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_pos = (pos[0] + direction[0], pos[1] + direction[1])
if self.labyrinth.is_valid_pos(next_pos):
if self._dfs(next_pos, path, visited):
return True
path.pop()
return False
# Esempio qui sotto:
shape = (10, 10)
start = (0, 0)
end = (9, 9)
labyrinth = Labyrinth(shape, start, end)
labyrinth.add_wall((2, 2))
labyrinth.add_wall((3, 2))
labyrinth.add_wall((4, 2))
labyrinth.add_wall((5, 2))
labyrinth.add_wall((5, 3))
labyrinth.add_wall((5, 4))
labyrinth.add_wall((4, 4))
labyrinth.add_wall((3, 4))
labyrinth.add_wall((2, 4))
navigator = Navigator(labyrinth)
path = navigator.solve()
print(path) # Output: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (5, 3), (5, 2), (4, 2), (3, 2), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9)]
