import random
from collections import deque


def generate_maze(w, h, seed=0):
    """
    Generate a randomized perfect maze using depth-first search.

    Args:
        w (int): width of the maze in cells (number of columns).
        h (int): height of the maze in cells (number of rows).

    Returns:
        list[list[int]]: 2D grid representing the maze where 1 indicates a wall
        and 0 indicates an open cell. The start is at (0,0) and the goal is at (w-1,h-1).
    """
    maze = [[1]*w for _ in range(h)]
    rng = random.Random(seed) if seed else None

    def dfs(x, y):
        maze[y][x] = 0
        dirs = [(0,2),(2,0),(0,-2),(-2,0)]
        (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs))
        for dx,dy in dirs:
            nx,ny = x+dx,y+dy
            if 0<=nx<w and 0<=ny<h and maze[ny][nx]:
                maze[y+dy//2][x+dx//2] = 0
                dfs(nx,ny)
                # occasional extra random connection (10%) to introduce loops and increase difficulty
                if (rng.random() if rng is not None else random.random()) < 0.1:
                    extra_dirs = [d for d in dirs if d != (dx,dy)]
                    (rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs))
                    for edx, edy in extra_dirs:
                        enx, eny = x+edx, y+edy
                        # ensure within bounds and target already open
                        if 0<=enx<w and 0<=eny<h and maze[eny][enx]==0:
                            # open the wall between (x,y) and (enx,eny) if it's closed
                            wx, wy = x+edx//2, y+edy//2
                            if maze[wy][wx]:
                                maze[wy][wx] = 0
                            break

    dfs(0,0)
    maze[0][0] = maze[h-1][w-1] = 0
    # ensure starting cell has one extra open neighbour if possible (not an external wall)
    dirs = [(0,2),(2,0),(0,-2),(-2,0)]
    random.shuffle(dirs)
    for dx,dy in dirs:
        nx,ny = dx,dy
        if 0<=nx<w and 0<=ny<h and maze[ny][nx]==1:
            # open the intermediate wall and the target cell
            maze[dy//2][dx//2] = 0
            maze[ny][nx] = 0
            break
    return maze


def generate_maze_iterative(w, h, seed=0):
    """
    Generate a randomized perfect maze using an explicit stack (iterative DFS).

    Args:
        w (int): width of the maze in cells (number of columns).
        h (int): height of the maze in cells (number of rows).

    Returns:
        list[list[int]]: 2D grid representing the maze where 1 indicates a wall
        and 0 indicates an open cell.
    """
    maze = [[1]*w for _ in range(h)]
    rng = random.Random(seed) if seed else None
    stack = [(0, 0)]
    maze[0][0] = 0
    dirs = [(0,2),(2,0),(0,-2),(-2,0)]
    while stack:
        x,y = stack[-1]
        (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs))
        for dx,dy in dirs:
            nx,ny = x+dx,y+dy
            if 0<=nx<w and 0<=ny<h and maze[ny][nx]:
                maze[y+dy//2][x+dx//2] = 0
                maze[ny][nx] = 0
                stack.append((nx,ny))
                # occasional extra random connection (10%) to introduce loops and increase difficulty
                if (rng.random() if rng is not None else random.random()) < 0.1:
                    extra_dirs = [d for d in dirs if d != (dx,dy)]
                    (rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs))
                    for edx, edy in extra_dirs:
                        enx, eny = x+edx, y+edy
                        if 0<=enx<w and 0<=eny<h and maze[eny][enx]==0:
                            wx, wy = x+edx//2, y+edy//2
                            if maze[wy][wx]:
                                maze[wy][wx] = 0
                            break
                break
        else:
            stack.pop()
    maze[0][0] = maze[h-1][w-1] = 0
    # ensure starting cell has one extra open neighbour if possible (not an external wall)
    dirs = [(0,2),(2,0),(0,-2),(-2,0)]
    (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs))
    for dx,dy in dirs:
        nx,ny = 0+dx, 0+dy
        if 0<=nx<w and 0<=ny<h and maze[ny][nx]==1:
            # open the intermediate wall and the target cell
            maze[dy//2][dx//2] = 0
            maze[ny][nx] = 0
            break
    return maze


def solve_maze(maze):
    """
    Solve a maze grid using breadth-first search to produce the shortest path.

    Args:
        maze (list[list[int]]): 2D grid where 1 indicates a wall and 0 indicates open space.

    Returns:
        list[tuple[int,int]]: list of (x, y) coordinates from start (0,0) to goal (w-1,h-1).
    """
    h,w = len(maze),len(maze[0])
    q = deque([(0,0)])
    parent = {(0,0):None}
    while q:
        x,y = q.popleft()
        if (x,y)==(w-1,h-1):
            break
        for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx,ny = x+dx,y+dy
            if 0<=nx<w and 0<=ny<h and maze[ny][nx]==0 and (nx,ny) not in parent:
                parent[(nx,ny)] = (x,y)
                q.append((nx,ny))
    path = []
    at = (w-1,h-1)
    while at:
        path.append(at)
        at = parent.get(at)
    return path[::-1]