# -*- coding: utf-8 -*-
"""
Corrigé Python - Bac NSI 2026 - Épreuve pratique - Sujet 14
Thème : simulation d'évacuation, grilles et distances de Manhattan
"""

from __future__ import annotations

from copy import deepcopy
from random import shuffle


class Piece:
    def __init__(self, profondeur: int, largeur: int) -> None:
        self.grille = [[0 for _ in range(largeur)] for _ in range(profondeur)]
        self.i_max = profondeur - 1
        self.j_max = largeur - 1
        self.capacite = profondeur * largeur * 5
        self.sorties = []

    def ajouter_occupants(self, i: int, j: int, nb: int) -> int:
        nb_add = min(nb, 5 - self.grille[i][j])
        if nb_add > 0:
            self.grille[i][j] += nb_add
        return nb_add

    def nb_occupants_restants(self) -> int:
        """Renvoie le nombre total d'occupants restants dans la pièce."""
        total = 0
        for ligne in self.grille:
            for case in ligne:
                total += case
        return total

    def ajouter_sortie(self, direction: str, position: int) -> None:
        """Ajoute une sortie au nord, au sud, à l'est ou à l'ouest."""
        if direction == "N":
            self.sorties.append((0, position))
        elif direction == "S":
            self.sorties.append((self.i_max, position))
        elif direction == "E":
            self.sorties.append((position, self.j_max))
        elif direction == "O":
            self.sorties.append((position, 0))

    def choix_sortie(self, i: int, j: int) -> tuple[int, int]:
        """Renvoie la sortie la plus proche de la case (i, j)."""
        assert len(self.sorties) > 0, "Aucune sortie"
        choix = self.sorties[0]
        distance = abs(i - choix[0]) + abs(j - choix[1])
        for autre_sortie in self.sorties[1:]:
            d2 = abs(i - autre_sortie[0]) + abs(j - autre_sortie[1])
            if d2 < distance:
                choix = autre_sortie
                distance = d2
        return choix

    def deplacer(self, i: int, j: int, nb: int, direction: str, silencieux: bool = True) -> int:
        d = {"N": (-1, 0), "S": (1, 0), "E": (0, 1), "O": (0, -1)}
        nv_i, nv_j = i + d[direction][0], j + d[direction][1]
        nb_dep = min(nb, 5 - self.grille[nv_i][nv_j], self.grille[i][j])
        if nb_dep > 0:
            self.grille[i][j] -= nb_dep
            self.grille[nv_i][nv_j] += nb_dep
        return nb_dep

    def alerter(self, silencieux: bool = True) -> bool:
        old_grille = deepcopy(self.grille)
        modif = False
        for i in range(len(self.grille)):
            for j in range(len(self.grille[i])):
                if old_grille[i][j] > 0:
                    sortie_i, sortie_j = self.choix_sortie(i, j)
                    dx, dy = sortie_j - j, sortie_i - i
                    if dx == 0 and dy == 0:
                        self.grille[i][j] -= 1
                        nb_dep = 1
                    else:
                        mvt_possibles = []
                        if dx > 0:
                            mvt_possibles.append("E")
                        elif dx < 0 and j > 0:
                            mvt_possibles.append("O")
                        if dy > 0:
                            mvt_possibles.append("S")
                        elif dy < 0 and i > 0:
                            mvt_possibles.append("N")
                        shuffle(mvt_possibles)
                        nb_dep = self.deplacer(i, j, old_grille[i][j], mvt_possibles[0], silencieux)
                        if nb_dep == 0 and len(mvt_possibles) > 1:
                            nb_dep = self.deplacer(i, j, old_grille[i][j], mvt_possibles[1], silencieux)
                    if nb_dep > 0:
                        modif = True
        return modif


def evacuation(p: Piece, silencieux: bool = True) -> int:
    """Simule l'évacuation et renvoie le nombre de tours nécessaires."""
    nb_tours = 0
    while p.nb_occupants_restants() > 0:
        deplacement = p.alerter(silencieux)
        nb_tours += 1
        if not deplacement:
            break
    return nb_tours


def tests() -> None:
    p = Piece(5, 7)
    assert p.nb_occupants_restants() == 0
    p.ajouter_occupants(0, 3, 4)
    p.ajouter_occupants(3, 4, 3)
    assert p.nb_occupants_restants() == 7
    p.ajouter_sortie("N", 5)
    p.ajouter_sortie("S", 1)
    p.ajouter_sortie("E", 3)
    p.ajouter_sortie("O", 1)
    assert p.sorties == [(0, 5), (4, 1), (3, 6), (1, 0)]
    assert p.choix_sortie(0, 3) == (0, 5)
    assert p.choix_sortie(3, 4) == (3, 6)
    print("Tous les tests du sujet 14 sont passés.")


if __name__ == "__main__":
    tests()