#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1110
Task: Write a Python function that generates a random maze and solves it with BFS
Generated: 2026-02-12T20:38:53.039714
"""

import random
from collections import deque

def generate_maze(width, height):
    maze = [['#' for _ in range(width)] for _ in range(height)]
    start = (1, 1)
    end = (height - 2, width - 2)
    maze[start[0]][start[1]] = 'S'
    maze[end[0]][end[1]] = 'E'

    # Directions: up, right, down, left
    directions = [( -2, 0), (0, 2), (2, 0), (0, -2)]

    # Use visited to track cells that have been visited
    visited = set()
    stack = [start]
    visited.add(start)

    while stack:
        x, y = stack[-1]
        random.shuffle(directions)
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < height and 0 <= ny < width and (nx, ny) not in visited:
                # Remove wall between (x, y) and (nx, ny)
                maze[(x + nx) // 2][(y + ny) // 2] = ' '
                maze[nx][ny] = ' '
                visited.add((nx, ny))
                stack.append((nx, ny))
                break
        else:
            stack.pop()

    return maze, start, end

def bfs_solve(maze, start, end):
    height = len(maze)
    width = len(maze[0])
    visited = set()
    queue = deque()
    queue.append((start[0], start[1], []))
    visited.add((start[0], start[1]))

    while queue:
        x, y, path = queue.popleft()
        path = path + [(x, y)]

        if (x, y) == end:
            return path

        # Directions: up, right, down, left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < height and 0 <= ny < width and maze[nx][ny] != '#' and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, path))

    return None  # No path found

def print_maze(maze):
    for row in maze:
        print(''.join(row))

def main():
    maze, start, end = generate_maze(11, 11)
    print("Generated Maze:")
    print_maze(maze)

    path = bfs_solve(maze, start, end)
    if path:
        print("\nSolution Path (BFS):")
        for x, y in path:
            maze[x][y] = 'P'
        print_maze(maze)
    else:
        print("No path found.")

if __name__ == '__main__':
    main()