Concours MP PSI - Exploration d'une grotte souterraine

def est_valide(grotte, ligne, col):
    N = len(grotte)
    M = len(grotte[0])
    if ligne < 0 or ligne >= N or col < 0 or col >= M:
        return False
    return grotte[ligne][col] != '#'

DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def voisins(grotte, ligne, col):
    resultat = []
    for dl, dc in DIRECTIONS:
        nl, nc = ligne + dl, col + dc
        if est_valide(grotte, nl, nc):
            case = grotte[nl][nc]
            poids = POIDS.get(case, 1)
            resultat.append(((nl, nc), poids))
    return resultat

def construire_graphe(grotte):
    graphe = {}
    N, M = len(grotte), len(grotte[0])
    for l in range(N):
        for c in range(M):
            if grotte[l][c] != '#':
                graphe[(l, c)] = voisins(grotte, l, c)
    return graphe

def localiser(grotte, symbole):
    positions = []
    for l, ligne in enumerate(grotte):
        for c, case in enumerate(ligne):
            if case == symbole:
                positions.append((l, c))
    return positions

from collections import deque

def bfs(graphe, depart):
    distances = {depart: 0}
    file = deque([depart])
    while file:
        courant = file.popleft()
        for (voisin, _) in graphe.get(courant, []):
            if voisin not in distances:
                distances[voisin] = distances[courant] + 1
                file.append(voisin)
    return distances

def dfs(graphe, depart):
    visites = []
    vus = set()
    pile = [depart]
    while pile:
        courant = pile.pop()
        if courant not in vus:
            vus.add(courant)
            visites.append(courant)
            for (voisin, _) in reversed(graphe.get(courant, [])):
                if voisin not in vus:
                    pile.append(voisin)
    return visites

def salles_accessibles(graphe, depart):
    return set(bfs(graphe, depart).keys())

def est_accessible(graphe, depart, arrivee):
    return arrivee in salles_accessibles(graphe, depart)

def chemin_court_bfs(graphe, depart, arrivee):
    predecesseur = {depart: None}
    file = deque([depart])
    while file:
        courant = file.popleft()
        if courant == arrivee:
            break
        for (voisin, _) in graphe.get(courant, []):
            if voisin not in predecesseur:
                predecesseur[voisin] = courant
                file.append(voisin)
    # Reconstruction du chemin
    if arrivee not in predecesseur:
        return []
    chemin = []
    salle = arrivee
    while salle is not None:
        chemin.append(salle)
        salle = predecesseur[salle]
    chemin.reverse()
    return chemin

import heapq

def dijkstra(graphe, depart):
    couts = {depart: 0}
    pred  = {depart: None}
    tas   = [(0, depart)]   # (cout, sommet)
    while tas:
        cout_courant, courant = heapq.heappop(tas)
        if cout_courant > couts.get(courant, float('inf')):
            continue   # entrée obsolète dans le tas
        for (voisin, poids) in graphe.get(courant, []):
            nouveau_cout = cout_courant + poids
            if nouveau_cout < couts.get(voisin, float('inf')):
                couts[voisin] = nouveau_cout
                pred[voisin]  = courant
                heapq.heappush(tas, (nouveau_cout, voisin))
    return couts, pred

def chemin_optimal(graphe, depart, arrivee):
    couts, pred = dijkstra(graphe, depart)
    if arrivee not in couts:
        return [], float('inf')
    # Reconstruction du chemin via les prédécesseurs
    chemin = []
    salle = arrivee
    while salle is not None:
        chemin.append(salle)
        salle = pred[salle]
    chemin.reverse()
    return chemin, couts[arrivee]

def chemin_sans_danger(graphe, grotte, depart, arrivee):
    # Identifier les salles dangereuses
    dangereuses = set(localiser(grotte, 'D'))
    # Construire un sous-graphe sans les salles dangereuses
    sous_graphe = {}
    for salle, voisins_liste in graphe.items():
        if salle in dangereuses:
            continue
        sous_graphe[salle] = [
            (v, p) for (v, p) in voisins_liste
            if v not in dangereuses
        ]
    return chemin_optimal(sous_graphe, depart, arrivee)

from itertools import permutations

def collecter_tresors(graphe, grotte, entree, sortie):
    tresors = localiser(grotte, 'T')
    if not tresors:
        # Pas de trésors : chemin direct
        chemin, cout = chemin_optimal(graphe, entree, sortie)
        return chemin, cout
    meilleur_cout   = float('inf')
    meilleur_chemin = []
    for perm in permutations(tresors):
        etapes = [entree] + list(perm) + [sortie]
        cout_total = 0
        chemin_total = [etapes[0]]
        valide = True
        for i in range(len(etapes) - 1):
            segment, cout = chemin_optimal(graphe, etapes[i], etapes[i+1])
            if not segment:
                valide = False
                break
            cout_total  += cout
            chemin_total += segment[1:]   # éviter la duplication du point de départ
        if valide and cout_total < meilleur_cout:
            meilleur_cout   = cout_total
            meilleur_chemin = chemin_total
    return meilleur_chemin, meilleur_cout

def zones_coupees(graphe, grotte):
    sommets = list(graphe.keys())
    disc = {}     # temps de découverte
    low  = {}     # low-link value
    parent = {}   # parent dans l'arbre DFS
    points = set()
    timer = [0]

    def dfs_articu(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        nb_enfants = 0
        for (v, _) in graphe.get(u, []):
            if v not in disc:
                nb_enfants += 1
                parent[v] = u
                dfs_articu(v)
                low[u] = min(low[u], low[v])
                # Racine avec ≥ 2 enfants → point d'articulation
                if parent.get(u) is None and nb_enfants > 1:
                    points.add(u)
                # Nœud non-racine : low[v] >= disc[u] → point d'articulation
                if parent.get(u) is not None and low[v] >= disc[u]:
                    points.add(u)
            elif v != parent.get(u):
                low[u] = min(low[u], disc[v])

    for s in sommets:
        if s not in disc:
            parent[s] = None
            dfs_articu(s)

    return sorted(points)

def plus_court_contournement(graphe, grotte, depart, arrivee, salle_bloquee):
    # Sous-graphe sans la salle bloquée
    sous_graphe = {}
    for salle, voisins_liste in graphe.items():
        if salle == salle_bloquee:
            continue
        sous_graphe[salle] = [
            (v, p) for (v, p) in voisins_liste
            if v != salle_bloquee
        ]
    return chemin_optimal(sous_graphe, depart, arrivee)

def afficher_chemin(grotte, chemin):
    # Copie profonde de la grotte
    copie = [list(ligne) for ligne in grotte]
    symboles_fixes = {'E', 'S', 'T', 'D', '#'}
    for (l, c) in chemin:
        if copie[l][c] not in symboles_fixes:
            copie[l][c] = '*'
    return copie

def print_grotte(grotte_affichee):
    for ligne in grotte_affichee:
        print(' '.join(ligne))

def rapport_exploration(grotte, graphe):
    N, M = len(grotte), len(grotte[0])
    entree = localiser(grotte, 'E')[0]
    sortie = localiser(grotte, 'S')[0]
    tresors    = localiser(grotte, 'T')
    dangereuses = localiser(grotte, 'D')
    # Salles totales (non '#')
    nb_totales = sum(
        1 for l in range(N) for c in range(M)
        if grotte[l][c] != '#'
    )
    # Salles accessibles depuis l'entrée
    accessibles = salles_accessibles(graphe, entree)
    # Chemins
    chemin_court   = chemin_court_bfs(graphe, entree, sortie)
    ch_opt, c_opt  = chemin_optimal(graphe, entree, sortie)
    ch_sur, c_sur  = chemin_sans_danger(graphe, grotte, entree, sortie)
    # Points d'articulation
    pa = zones_coupees(graphe, grotte)
    # Itinéraire complet (avec trésors)
    itin, c_itin = collecter_tresors(graphe, grotte, entree, sortie)
    return {
        'nb_salles_totales'    : nb_totales,
        'nb_salles_accessibles': len(accessibles),
        'nb_tresors'           : len(tresors),
        'nb_salles_dangereuses': len(dangereuses),
        'entree'               : entree,
        'sortie'               : sortie,
        'chemin_court'         : chemin_court,
        'longueur_chemin_court': len(chemin_court) - 1 if chemin_court else -1,
        'chemin_optimal'       : ch_opt,
        'cout_chemin_optimal'  : c_opt,
        'chemin_sans_danger'   : ch_sur,
        'cout_sans_danger'     : c_sur,
        'points_articulation'  : pa,
        'tresors_collectes'    : tresors,
        'itineraire_complet'   : itin,
        'cout_itineraire'      : c_itin,
    }