import random

def go(maze, m, n, target, start, max_steps):
	"""Ищет цель в лабиринте, возвращает список ячеек Path или None"""
	visited = set()
	path = [start]
	visited.add(start)

	directions = [(1, 0), (-1, 0), # X
				  (0, 1), (0, -1)] # Y

	current = start
	while current != target and len(path) <= max_steps:
		x, y = current

		neighbors = []
		unvisited_neighbors = []
		for (dx, dy) in directions:
			nx, ny = x + dx, y + dy
			if is_free(nx, ny, maze, m, n):
				neighbors.append((nx, ny))
				if (nx, ny) not in visited:
					unvisited_neighbors.append((nx, ny))
		
		if not neighbors: # тупик
			return None 
		elif unvisited_neighbors:
			# Если есть непосещённые, выбираем случайное из них
			next_cell = random.choice(unvisited_neighbors)
		else:
			# Иначе выбираем из всех доступных
			next_cell = random.choice(neighbors)

		current = next_cell
		visited.add(current)
		path.append(current)

	return path if (current == target) else None

def generate_maze(m, n, start, target, wall_prob):
	"""Генерирует лабиринт со случайными стенами, исключая стартовую и целевую ячейки."""
	maze = [[True for _ in range(n)] for _ in range(m)]
	for x in range(m):
		for y in range(n):
				if (x, y) != start and (x, y) != target:
					if random.random() < wall_prob:
						maze[x][y] = False
	return maze

def is_free(x, y, maze, m, n):
	"""Проверяет, является ли ячейка свободной (True)"""
	return 0 <= x < m and 0 <= y < n and maze[x][y]


def display_maze(maze, m, n, target, title="Maze", path=[]):
	"""Визуализирует карту с маршрутом."""
	print(f"\n--- {title} ---")
	for x in range(m):
		sign = ""
		for y in range(n):
			coord = (x, y)
			if coord == target:
				sign += " O"
			elif maze[x][y] == False:
				sign += " #"
			elif coord in path:
				sign += " ."
			else:
				sign += "  "
		print(sign)

# тело программы
if __name__ == "__main__":

	M, N = random.randint(5,15), random.randint(5,15) # Размеры лабиринта 
	start = (0, 0) # Начальная позиция 
	max_steps = 1000 # Максимальная дальность пути 
	target = (random.randint(0, M-1), random.randint(0, N-1))

	# Генерация лабиринта. True - ячейка пустая, False - камень/стена
	maze = generate_maze(M, N, start, target, wall_prob=0.2)

	# Отображение оригинального лабиринта
	display_maze(maze, M, N, target, "Maze")

	# запуск алгоритма поиска цели 
	path = go(maze, M, N, target, start, max_steps)

	if path:
		# Цель найдена. Отображение карты с маршрутом 
		display_maze(maze, M, N, target, "Path", path)
		print(f"\nЦель найдена за {len(path) - 1} шагов.")
	else:
		print(f"\nНе удалось найти цель.")