from __future__ import annotations
import random
from typing import List, Optional, Tuple

Celle = Tuple[int, int] # (x, y)

class Labyrint:
    def __init__(self, kolonner: int, rader: int):
        if kolonner < 3 or rader < 3:
            raise ValueError("Kolonner og rader m? v?re >=3")
        self._kolonner = kolonner
        self._rader = rader
        self._rutenett: List[List[int]] = [[1 for _ in range(kolonner)] for _ in range(rader)]
        self._besokt: List[List[bool]] = [[False for _ in range(kolonner)] for _ in range(rader)]
        self._inngang: Optional[Celle] = None
        self._utgang: Optional[Celle] = None

    def generer(self, seed: Optional[int] = None) -> None:
        if seed is not None:
            random.seed(seed)
        for y in range(self._rader):
            for x in range(self._kolonner):
                self._rutenett[y][x] = 1
                self._besokt[y][x] = False

        start_x = random.randint(1, self._kolonner - 2)
        start_y = random.randint(1, self._rader - 2)

        stabel: List[Celle] = [(start_x, start_y)]
        self._rutenett[start_y][start_x] = 0

        while stabel:
            x, y = stabel[-1]
            self._besokt[y][x] = True

            naboer = []
            for dx, dy in [(0, 2), (0, -2), (2, 0), (-2, 0)]:
                nx, ny = x + dx, y + dy
                if 1 <= nx < self._kolonner - 1 and 1 <= ny < self._rader - 1 and not self._besokt[ny][nx]:
                    naboer.append((nx, ny, dx, dy))

            if naboer:
                nx, ny, dx, dy = random.choice(naboer)
                self._rutenett[ny][nx] = 0
                self._rutenett[y + dy // 2][x + dx // 2] = 0
                stabel.append((nx, ny))
            else:
                stabel.pop()

        self._sett_inngang_og_utgang()

    def _sett_inngang_og_utgang(self) -> None:
        cols, rows = self._kolonner, self._rader

        # Kandidater p? kanten der den indre naboen er sti
        toppstier    = [(x, 0)        for x in range(cols) if self._rutenett[1][x] == 0]
        bunnstier = [(x, rows - 1) for x in range(cols) if self._rutenett[rows - 2][x] == 0]
        ventrestier   = [(0, y)        for y in range(rows) if self._rutenett[y][1] == 0]
        hoyrestier  = [(cols - 1, y) for y in range(rows) if self._rutenett[y][cols - 2] == 0]

        def aapne_celle(cell: Celle) -> None:
            x, y = cell
            self._rutenett[y][x] = 0  # VIKTIG: ?pne selve randcellen

        if toppstier and bunnstier:
            self._inngang = random.choice(toppstier)
            self._utgang = random.choice(bunnstier)
            aapne_celle(self._inngang)
            aapne_celle(self._utgang)

        elif ventrestier and hoyrestier:
            self._inngang = random.choice(ventrestier)
            self._utgang = random.choice(hoyrestier)
            aapne_celle(self._inngang)
            aapne_celle(self._utgang)

        else:
            # Fallback: velg to tilfeldige kantstier eller lag hull
            alle_kantstier = toppstier + bunnstier + ventrestier + hoyrestier
            if len(alle_kantstier) >= 2:
                self._inngang, self._utgang = random.sample(alle_kantstier, 2)
                aapne_celle(self._inngang)
                aapne_celle(self._utgang)
            else:
                # Siste utvei: s?rg for at det finnes ?pninger
                self._inngang = (1, 0)
                self._utgang = (cols - 2, rows - 1)
                aapne_celle(self._inngang)
                aapne_celle(self._utgang)

    def hent_rutenett(self) -> List[List[int]]:
        return self._rutenett

    def hent_ingang_og_utgang(self) -> Tuple[Optional[Celle], Optional[Celle]]:
        return self._inngang, self._utgang